題目

給定一個(gè)數(shù)組?prices?，它的第?i?個(gè)元素?prices[i]?表示一支給定股票第?i?天的價(jià)格。

你只能選擇?某一天?買入這只股票，并選擇在?未來(lái)的某一個(gè)不同的日子?賣出該股票。設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。

返回你可以從這筆交易中獲取的最大利潤(rùn)。如果你不能獲取任何利潤(rùn)，返回?0?。

示例 1：

輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤(rùn) = 6-1 = 5 。注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)，你不能在買入前賣出股票。

示例 2：

輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

解答

源代碼

class Solution {public int maxProfit(int[] prices) {int minPrice = Integer.MAX_VALUE;int maxProfit = 0;for (int i = 0; i < prices.length; i++) {if (prices[i] < minPrice) {minPrice = prices[i];} else if (prices[i] - minPrice > maxProfit) {maxProfit = prices[i] - minPrice;}}return maxProfit;}
}

總結(jié)

盡量拒絕暴力破解，遍歷一次，不斷更新最低價(jià)和能夠獲得的最大利潤(rùn)，返回最終的最大利潤(rùn)。