一、引言

這是一道非常有趣的題目！
這是一道非常有趣的題目！！
這是一道非常有趣的題目！！！

重要的事情先說三遍 : )

好了，接下來讓我們看看這道題：

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

這道題居然沒有例子？！ T_T，然后還有一大段的英文描述~~~

說實話，我第一次看到這道題，拿著百度翻譯看題目居然都沒有看懂，然后逐字逐句拿著程序運行查看正確結果后才弄清楚了題意，現在翻譯如下：

話說你現在有一個數組，這個數組呢，第 i 個元素就是給定貨物第 i 天的價格信息。

請你設計一個算法能夠達到最高的收益。你需要完成你想要的交易（比如，先買入貨物然后再賣出貨物多次）。然而，你只能在同一天交易一次（買入或者賣出），并且你在賣出貨物之前，必須要先買入貨物。

為了避免你們只讀了題目無法理清楚頭緒（我也是通過提交空代碼查看 Expected Answer 才弄清楚題意的），我還是舉個我自己的例子來說明下什么叫做最大的收益：

舉例：

[2, 4, 1, 0, 1, 0, 3]

看看這個例子，或許有些極端（這個貨物在某些天居然是 0 價格~~~），我們來看看我們如何在 7 天（給定數組的長度）內得到最大收益：

第幾天貨物價格我們的選擇收益

一	2	看到第二天價格升高，今天我們買入	-2
二	4	看到第三天價格降低，今天我們賣出	+4
三	1	看到第四天價格降低，今天我們什么也不做	+0
四	0	看到第五天價格升高，今天我們買入	-0
五	1	看到第六天價格降低，今天我們賣出	+1
六	0	看到第七天價格升高，今天我們買入	-0
七	3	今天是最后一天，賣出我們手上的貨物	+3

這個表格非常清晰地說明了我們作為一個追求利益最大化的商人是如何處理手上的資本不斷進行貨物的買入賣出從而得到利益的。

仔細感受下這個過程，能不能總結出來一個所有情況適用的規律呢？總結不出來也沒關系，我也不是一下子就總結出來的，讓我們再認真想想：

首先，我們一直在看的，都是后面的價格，也就是說前面的價格信息對于我們的行為沒有任何影響。很好，這里我們獲得了第一個信息：我們在一次買入和賣出行為時，只關心后面的價格信息

然后，我們總是在最高價格的時候賣出的嗎？如果是這樣的話，我們為什么要在第五天進行賣出呢（第五天的價格并非最高價格）。那么我們是什么時候才進行賣出呢？仔細看看價格規律，看到了嗎，我們總是在知道明天會降價的時候，我們才會當天賣出！很好，這里我們得到了一個至關重要的信息：我們總是在明天要降價的情況下賣出手上的貨物

最后，那么我們在何時買入貨物呢？同樣的道理，我們也不是在最低價格的時候買入（與第 2 條同樣的道理），我們是在剛賣出之后，得知后面會漲價的時候，我們才會進行貨物的買入操作！很好，我們又獲得了一個非常重要的信息：我們總是在知道明天會漲價的情況下買入貨物

相信只要你仔細看到了這里，這道題的題意你一定已經弄清楚了，那么就讓我們思考下，這道題到底應該怎么做呢？

二、簡單的抽象：買入賣出行為背后的映射

在引言里，我通過舉例闡述了題意，并且詳細分析了作為一個追求利益最大化的商人在每一天的行為。

那么商人的買入賣出行為能不能抽象為我們的代碼邏輯呢？

還是讓我們再看向引言里我舉的例子，總結下我們找到的這三條關鍵信息：

我們在一次買入和賣出行為時，只關心后面的價格信息

我們總是在明天要降價的情況下賣出手上的貨物

我們總是在知道明天會漲價的情況下買入貨物

讓我們仔細看看這三條信息，“我們只有在知道明天要降價的情況下賣出” 和 “我們只有在知道明天要漲價的情況下買入”，那么如果我們將買入和賣出看作一個單元操作的話：

從買入到賣出貨物的過程中，貨物的價格總是呈上升趨勢

也就是說，只有當我們做到了在價格變化的最低點買入貨物，在價格變化的最高點賣出貨物，我們才能得到最大的收益。

那么，這個規律相對于程序設計層面上的抽象是什么呢：

將價格數組分割為這樣的小數組：每個小數組都是順序增大的；在每個數組中，我們在左邊的最小值進行買入，右邊的最大值進行賣出

如果你還沒懂的話，我這里簡單畫了一個圖進行闡述：

這里，我們只需要將每個小數組的最右邊的元素減去最左邊的元素即可得到一次買入賣出的收益值。

經過我們的分析，代碼其實就已經出來了：

// my solution 1 , runtime = 6 ms class Solution1 { public:int maxProfit(vector<int>& prices) {if (prices.size() <= 1) return 0;auto preIt = prices.begin();vector<int> split;int profit = 0;for (auto curIt = prices.begin() + 1; curIt != prices.end(); ++preIt, ++curIt)if (*preIt > *curIt) split.push_back(preIt - prices.begin());if (split.size() == 0) profit = prices[prices.size() - 1] - prices[0];else {for (int i = 0; i < split.size(); ++i) {if (i == 0) profit += prices[split[0]] - prices[0];else profit += prices[split[i]] - prices[split[i - 1] +1];}profit += prices[prices.size() - 1] - prices[split[split.size() - 1] + 1];}return profit;} };

這段代碼比較復雜，這里好好解釋下：

首先，我們要明確我們要干嘛，我們需要分割數組，怎么分割呢？按照“上一個元素值大于了下一個元素的值”為標準進行分割，所以我們需要兩個指針對數組進行遍歷，因此，我們需要做的第一步就是判斷數組是否有至少 1 個元素

然后，我們明確了數組含有至少 1 個元素，我們聲明兩個指針（迭代器），對參數數組 prices 進行遍歷，當 preIt 指向的元素值大于了 curIt 指向的元素值，我們就將這個 preIt（也就是一個數組的最右邊的分割地）記入我們的分割記錄 split 中；直到我們遍歷結束，我們也就擁有了數組中間（無開頭和結尾）的分割記錄 split 數組

最后，我們需要拿著分組信息計算我們的最大收益值；第一步，我們需要判斷分組數組的大小，如果沒有分組信息，那么證明價格數組就是規律排序的數組，那么只需要拿價格數組的最右邊減去最左邊即可；如果有分組信息，我們就需要將各個分組中的最右邊減去最左邊的值（其中第一個分組的最左邊是價格數組的第一個元素，最后一個分組的最右邊是價格數組的最后一個元素）遞加；最后我們返回我們計算的收益值即可

怎么樣，相信經過了我的圖文并茂的解釋，你應該理解了這段代碼的邏輯。

如果你是自己通過分析做出來這道題的，那么從讀題到抽象，從抽象到代碼實現，都是一個非常有趣的過程~~~

三、更優的追求：邏輯、代碼的簡化

還有沒有其他的方法呢？

這里我想到了一點優化的方案：上一個方法我們分割了數組，將分割信息存儲到了 split 數組（split 數組中存儲的是位置信息而非價格信息，不能直接用作計算）中去，最后從這個 split 數組中讀取數據時處理處理下標處理時有點復雜，能不能簡化些呢？

答案當然是可以的：

這里我利用兩個數組，前者 buy 數組記錄買入日期的價格，后者 sell 數組記錄賣出日期的價格，這樣我們最后只需要對這個數組進行整合計算即可，代碼如下：

// my solution 2 , runtime = 13 ms class Solution2 { public:int maxProfit(vector<int>& prices) {if (prices.size() <= 1) return 0;vector<int> buy;vector<int> sell;int profit = 0;buy.push_back(prices[0]);for (auto pre = prices.begin(), cur = prices.begin() + 1; cur != prices.end(); ++pre, ++cur)if (*pre > *cur) {buy.push_back(*cur);sell.push_back(*pre);}sell.push_back(prices[prices.size() - 1]);if (buy.size() == 1 && sell.size() == 1) return prices[prices.size() - 1] - prices[0];for (int i = 0; i < buy.size(); ++i)profit += sell[i] - buy[i];return profit;} };

代碼邏輯和上一個方法是一樣的，只是下面這種方法呢，在計算差值的時候能更加簡便些。

那么還沒有其他的方法呢？我實在是不想再處理數組下標了！

答案當然是有的。

這里我使用了 std::queue 實現了另一個版本的代碼，思路與上述方法都是一樣的，直接看代碼吧：

// my soluiton 3 use std::queue , runtime = 6 ms class Solution3 { public:int maxProfit(vector<int>& prices) {if (prices.size() <= 1) return 0;int profit = 0;queue<int> stock;for (auto i : prices) {if (stock.empty() || stock.back() < i) {stock.push(i);}else {profit += stock.back() - stock.front();while (!stock.empty()) stock.pop();stock.push(i);}}profit += stock.back() - stock.front();return profit;} };

顧名思義， std::queue 也就是隊列，這個版本的實現方法與上述方法的思路沒有什么不同，只是處理數據的數據結構更換成了隊列。

為什么使用隊列呢？因為對于這種只處理頭跟尾數據的情況，我思考覺得使用隊列是最適合的。

關于 std::queue 還是有必要說一下的，比如說這里：

while (!stock.empty()) stock.pop();

其實這里還可以簡化為：

// C++11 stock = {};

那么這里為什么要這么寫呢？不能直接使用 clear() 方法嗎？

對的，std::queue 還真的不支持 clear() 操作，別說它，甚至 std::stack 也不支持，那么這是為什么呢？

這段解釋來源于 StackOverflow 社區，感興趣的同學可以點擊這里 why std::queue doesn’t support clear() function?。

這段話比較生澀，我盡自己最大的努力翻譯一下：

隊列是一種適配器容器，是一種使用了特殊的密封容器作為它的底層實現的容器，提供特殊訪問底層容器的一些方法。

這也意味著隊列使用的是已經存在的容器，它也確實只是這個容器的實現 FIFO （先進先出）的接口類而已。

這也就解釋了隊列不能使用清空操作的原因。如果你需要清空一個隊列，那么這意味著你實際上需要的是一個實體類而非隊列，所以你應該使用底層容器來替代而非一個隊列。

這里翻譯的非常生澀，麻煩大家忍痛看看哈 ~~~ 大概含義也解釋清楚了，這里使用 std::queue 明顯使我們的問題直接簡化了一個數量級，可謂是體會到了數據結構的威力。

盡管想了很久很久，能不能再優化再優化，還是黔驢技窮了 T_T ~~~

也罷，讓我們看看最高票答案的簡潔優雅吧！

四、簡潔的美：誰叫我是最高票答案呢

既然你已經耐心的看到了這里，那么我也就大發慈悲地拿出了最高票答案來震撼震撼你的心靈 ：

// perfect solution tree lines code class Solution4 { public:int maxProfit(vector<int> &prices) {int ret = 0;for (size_t p = 1; p < prices.size(); ++p)ret += max(prices[p] - prices[p - 1], 0);return ret;} };

什么！只有這么幾行代碼？！
什么！這里的 std::max 是干什么用的？！

讓我們看看作者的解釋吧：

suppose the first sequence is “a <= b <= c <= d”, the profit is “d - a = (b - a) + (c - b) + (d - c)” without a doubt. And suppose another one is “a <= b >= b’ <= c <= d”, the profit is not difficult to be figured out as “(b - a) + (d - b’)”. So you just target at monotone sequences.

簡單翻譯下：

假定第一種順序是這樣的： a <= b <= c <= d，那么此時的收益值為：d - a = (b - a) + (c - b) + (d - c)，這一點毋容置疑（這一塊只要你理解了我之前的邏輯，這個式子很好理解）；現在假想第二種順序：a <= b >= b’ <= c <= d，那么現在的收益值應該不難得出為：(b - a) + (d - b)。那么你就可以得到結果了。

說實話，這個方法理解起來比較難但是我們把第二種順序的收益值計算方式分開：

(b - a) + (d - c) == (b - a) + (c - b’) + (d - c)

看到這里如果你還不明白，就跟著代碼走一遍 a <= b >= b’ <= c <= d 順序就知道結果是怎么出來的了。

我的天！
太神奇了！
真心覺得巧妙，作者一定是一個數學天才！在這里給這段代碼的作者點 999+ 個贊~~~

五、總結

這道題我做了好久好久，從一開始的分析，到之后做出了第一個方法，然后開始思考如何優化代碼，之后思考出來了使用隊列；再之后思考不出來更優的辦法了，點開看了看最高票答案，又一次心靈受到了強烈的震撼；真是一次奇妙的體驗啊。

寫了三個版本的代碼，又體驗了一把 std::queue，自己的體驗來說，收獲還是很多的；最高票答案雖說非常巧妙，可是我覺得要是直接寫出了最高票答案其實難免覺得有點不盡興。因為其他沒想到這個方法的人，繞了太陽系走了一大圈，最終走到了目的地，雖說不如最高票答案簡潔優雅，卻也是提升了不少技能點呢~~~

這篇博客也寫了好久，認認真真地寫清楚了自己的實現邏輯，因為自己的能力不足，在代碼的編寫上，邏輯的分析上，甚至部分英文的翻譯上難免有些出入，請各位讀者諒解。

最后的最后，獻給每一個正在辛苦刷 LeetCode 的人：

To be Stonger!

總結

以上是生活随笔為你收集整理的LeetCode之路：122. Best Time to Buy and Sell Stock II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。