通知：我已經(jīng)將刷題指南全部整理到了Github ：
https://github.com/youngyangyang04/leetcode-master，方便大家在電腦上閱讀，這個(gè)倉(cāng)庫(kù)每天都會(huì)更新，大家快去給一個(gè)star支持一下吧！

121. 買賣股票的最佳時(shí)機(jī)

題目鏈接：https:///problems/best-time-to-buy-and-sell-stock/

給定一個(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。

思路

暴力

這道題目最直觀的想法，就是暴力，找最優(yōu)間距了。

• 時(shí)間復(fù)雜度：O(n^2)

• 空間復(fù)雜度：O(1)

當(dāng)然該方法超時(shí)了。

貪心

因?yàn)楣善本唾I賣一次，那么貪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利潤(rùn)。

C++代碼如下：

class Solution {public:    int maxProfit(vector<int>& prices) {        int low = INT_MAX;        int result = 0;        for (int i = 0; i < prices.size(); i++) {            low = min(low, prices[i]);  // 取最左最小價(jià)格            result = max(result, prices[i] - low); // 直接取最大區(qū)間利潤(rùn)        }        return result;    }};

• 時(shí)間復(fù)雜度：O(n)

• 空間復(fù)雜度：O(1)

動(dòng)態(tài)規(guī)劃

動(dòng)規(guī)五部曲分析如下：

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i][0] 表示第i天持有股票所得現(xiàn)金 ，這里可能有同學(xué)疑惑，本題中只能買賣一次，持有股票之后哪還有現(xiàn)金呢？

其實(shí)一開(kāi)始現(xiàn)金是0，那么加入第i天買入股票現(xiàn)金就是 -prices[i]， 這是一個(gè)負(fù)數(shù)。

dp[i][1] 表示第i天不持有股票所得現(xiàn)金

注意這里說(shuō)的是“持有”，“持有”不代表就是當(dāng)天“買入”！也有可能是昨天就買入了，今天保持持有的狀態(tài)

很多同學(xué)把“持有”和“買入”沒(méi)分區(qū)分清楚。

在下面遞推公式分析中，我會(huì)進(jìn)一步講解。

1. 確定遞推公式

如果第i天持有股票即dp[i][0]， 那么可以由兩個(gè)狀態(tài)推出來(lái)

• 第i-1天就持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天持有股票的所得現(xiàn)金 即：dp[i - 1][0]

• 第i天買入股票，所得現(xiàn)金就是買入今天的股票后所得現(xiàn)金即：-prices[i]

那么dp[i][0]應(yīng)該選所得現(xiàn)金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1]， 也可以由兩個(gè)狀態(tài)推出來(lái)

• 第i-1天就不持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 即：dp[i - 1][1]

• 第i天賣出股票，所得現(xiàn)金就是按照今天股票佳價(jià)格賣出后所得現(xiàn)金即：prices[i] + dp[i - 1][0]

同樣dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

這樣遞歸公式我們就分析完了

1. dp數(shù)組如何初始化

由遞推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出

其基礎(chǔ)都是要從dp[0][0]和dp[0][1]推導(dǎo)出來(lái)。

那么dp[0][0]表示第0天持有股票，此時(shí)的持有股票就一定是買入股票了，因?yàn)椴豢赡苡星耙惶焱瞥鰜?lái)，所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票，不持有股票那么現(xiàn)金就是0，所以dp[0][1] = 0;

1. 確定遍歷順序

從遞推公式可以看出dp[i]都是有dp[i - 1]推導(dǎo)出來(lái)的，那么一定是從前向后遍歷。

1. 舉例推導(dǎo)dp數(shù)組

以示例1，輸入：[7,1,5,3,6,4]為例，dp數(shù)組狀態(tài)如下：

dp[5][1]就是最終結(jié)果。

為什么不是dp[5][0]呢？

因?yàn)楸绢}中不持有股票狀態(tài)所得金錢一定比持有股票狀態(tài)得到的多！

以上分析完畢，C++代碼如下：

• 時(shí)間復(fù)雜度：O(n)

• 空間復(fù)雜度：O(n)

從遞推公式可以看出，dp[i]只是依賴于dp[i - 1]的狀態(tài)。

dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

那么我們只需要記錄 當(dāng)前天的dp狀態(tài)和前一天的dp狀態(tài)就可以了，可以使用滾動(dòng)數(shù)組來(lái)節(jié)省空間，代碼如下：

• 時(shí)間復(fù)雜度：O(n)

• 空間復(fù)雜度：O(1)

這里能寫出版本一就可以了，版本二雖然原理都一樣，但是想直接寫出版本二還是有點(diǎn)麻煩，容易自己給自己找bug。

所以建議是先寫出版本一，然后在版本一的基礎(chǔ)上優(yōu)化成版本二，而不是直接就寫出版本二。

PDF開(kāi)放下載

以下資源由「代碼隨想錄」原創(chuàng)出品！