小白學(xué)算法：買賣股票的最佳時(shí)機(jī)！

題目描述

注意：你不能在買入股票前賣出股票。

輸入: [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í)，你不能在買入前賣出股票。

輸入: [7,6,4,3,1]

輸出: 0

解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。

來(lái)源：LeetCode

劍指 offer 64：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/submissions/難度：中

leetcode 121：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/難度：簡(jiǎn)單

解題思路

但這有一個(gè)問(wèn)題，就是我們要保證最高價(jià)格要在最低的價(jià)格之后，因?yàn)槲覀儽仨氃谫?gòu)買了股票之后才能賣出，而不是相反的順序，這就讓問(wèn)題變的復(fù)雜了

但此刻我們想到了一個(gè)最直接也是最笨的一個(gè)方法，那就是用暴力窮舉法，我們使用兩層循環(huán)，依次在每個(gè)節(jié)點(diǎn)買入，然后再在之后的所有節(jié)點(diǎn)賣出，這樣來(lái)計(jì)算節(jié)點(diǎn)間的差值（收益），如果此差值大于當(dāng)前最高收益，就將此值設(shè)置為當(dāng)前最高收益，這樣循環(huán)完，我們就能獲得最大收益了。如下圖所示：

方法一：暴力法

class?Solution?{
????public?int?maxProfit(int[]?prices)?{
????????int?mp?=?0;?//?最高收益
????????for?(int?i?=?0;?i?????????????for?(int?j?=?i?+?1;?j?????????????????int?item?=?prices[j]?-?prices[i];
????????????????if?(item?>?mp)?mp?=?item;
????????????}
????????}
????????return?mp;
????}
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n^2)，循環(huán)運(yùn)行 n(n-1)/2 次。
• 空間復(fù)雜度：O(1)，只使用了常數(shù)位的變量。

方法二：遍歷一次

• 判斷當(dāng)前節(jié)點(diǎn)是不是相對(duì)最低價(jià)，如果是，則將它設(shè)置為最低價(jià)（也就是買入）；
• 如果當(dāng)前節(jié)點(diǎn)不是最低價(jià)，那我們就將它賣出，然后計(jì)算賣出的收益（當(dāng)前節(jié)點(diǎn)減去相對(duì)最低價(jià)），如果賣出的收益大于目前的最高收益，則將此值設(shè)置為最高收益。

class?Solution?{
????public?int?maxProfit(int?prices[])?{
????????if?(prices?==?null?||?prices.length?==?0)?return?0;
????????int?mp?=?0;?//?最高收益
????????int?min?=?prices[0];?//?最低價(jià)
????????for?(int?i?=?1;?i?????????????if?(prices[i]?????????????????//?設(shè)定相對(duì)最低價(jià)
????????????????min?=?prices[i];
????????????}?else?if?(mp?????????????????//?設(shè)定最高盈利
????????????????mp?=?prices[i]?-?min;
????????????}
????????}
????????return?mp;
????}
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，只需要遍歷一次。
• 空間復(fù)雜度：O(1)，只使用了常數(shù)個(gè)變量。

總結(jié)