LeetCode上關(guān)于買賣股票的問題一共有五道，題號分別為121，122，123，188，309。

此類問題的基本描述即給出一個序列prices[]，prices[i]代表第i天股票的價格。

如果當(dāng)天之前不持有股票，則可以以prices[i]的價格購入股票；

如果當(dāng)天之前持有股票，則可以以prices[i]的價格賣出股票；

當(dāng)然，當(dāng)天也可任何操作都不進(jìn)行。

目的就是求該階段的最大收益。

接下來我們根據(jù)每道題的約束條件不同，從易到難逐個分析這五個問題。

一、Best Time to Buy and Sell Stock??

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4] Output: 5max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1] Output: 0In this case, no transaction is done, i.e. max profit = 0.

本問題的約束即整個過程只能進(jìn)行一次買賣操作。

采取兩個變量in和out來記錄第i買入stock的最小代價和賣出stock的最大價格，如果 out-in>ans，則將ans更新為out-in。

時間復(fù)雜度O(n)，空間復(fù)雜度O(1)

public int maxProfit(int[] prices) {int len = prices.length;if (len == 0 || len == 1) return 0;int in = prices[0], out = prices[0], ans = 0;for (int i = 1; i < len; i++) {in = Math.min(in, prices[i]);out = Math.max(in, prices[i]);ans = out-in>ans ? out-in:ans;}return ans; }

二、Best Time to Buy and Sell Stock II??

Say you have an array for which the?ith?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).

本問題即可以盡可能多的進(jìn)行買賣操作，但是還是要保證買之前不持stock，賣之前持有stock。

此時該問題轉(zhuǎn)化為一個貪心問題（五個問題中唯一一個貪心，其他都是DP），貪心準(zhǔn)則很簡單：只要當(dāng)天比前一天股價高，則以前一天的價格買入并且當(dāng)天賣出。

看似存在兩個問題：

1. 題目要求當(dāng)天不能同時買賣，如果對于 [1, 3, 7] 這樣的情況，是不是違背了約束？當(dāng)然不是，對于這樣的單調(diào)序列，無論內(nèi)部長度多長，最大收益始終由首和尾兩個元素確定，而該收益完全等價于相鄰兩天價格差的和。

2. 對于[1, 5, 3, 9]這樣的非單調(diào)序列，是否找到的是真正的最大收益？是的，對于任意一個非單調(diào)序列，必然由若干個單調(diào)增序列和若干個單調(diào)減序列組成，故可以找到最大收益。

解決了這兩個問題，可有時間復(fù)雜度O(n)，空間復(fù)雜度O(1)的代碼：

public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) return 0;int ans = 0;for (int i = 1; i< len; i++) {if (prices[i]>prices[i-1]) ans += prices[i]-prices[i-1];}return ans;}

三、Best Time to Buy and Sell Stock III??

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

Design an algorithm to find the maximum profit. You may complete at most?two?transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

本問題相對于I，將只能完成一筆買賣操作的約束更改為至多可以完成兩筆買賣操作。

比較直觀的想法是找出這樣一個斷點i，該斷點前記為第一筆買賣，該斷點后記為第二筆買賣。

可以借用I中的想法正向算出各個時間段的第一筆買賣的最大收益；

對于各個時間段第二筆買賣的最大收益可以采取反向的方法：從prices[]數(shù)組尾端開始向前掃描，用out2記錄能賣出的最高價，注意此時只能以prices[i]的價格買入，而不能用in2記錄能買入的最低價，比如[2, 6,1]這樣的序列就會有問題。

這樣的想法的時間復(fù)雜度為O(n)，空間復(fù)雜度也為O(n)：

public int maxProfit(int[] prices) {int len = prices.length;if (len == 0 || len == 1) return 0;int in1 = prices[0], out1 = prices[0];int in2 = prices[len-1], out2 = prices[len-1];int[] ans1 = new int[len];int[] ans2 = new int[len];for (int i = 1, j = len-2; i < len; i++, j--) {in1 = Math.min(in1, prices[i]);out1 = Math.max(in1, prices[i]);ans1[i] = out1-in1>ans1[i-1] ? out1-in1:ans1[i-1];in2 = prices[j];ans2[j] = out2-in2>ans2[j+1] ? out2-in2:ans2[j+1];out2 = Math.max(out2, prices[j]);}int ans = Math.max(ans1[len-1], ans2[0]);for (int i = 1; i < len-1; i++) {ans = Math.max(ans1[i]+ans2[i+1], ans);}return ans;}

下面介紹一下別人 時間復(fù)雜度為O(n)，空間復(fù)雜度為 O(1)的方法：

分別用hold1、hold2記錄第一筆和第二筆買賣購入時的手中最大的錢數(shù)，用release1、release2記錄第一筆和第二筆買賣賣出時的手中最大的錢數(shù)。

則hold1即取時刻i之前的最低股票價即可，release1取第i時刻之前的hold1+prices[i]和release1大者；

hold2取時刻i之前完成第一筆買賣即release1減去當(dāng)前股票價格和hold2大者，release2用release1的方法更新即可。

需要注意的是每個時刻這四個變量更新的順序。

public int maxProfit(int[] prices) {int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;int release1 = 0, release2 = 0;for(int i:prices){ // Assume we only have 0 money at firstrelease2 = Math.max(release2, hold2+i); // The maximum if we've just sold 2nd stock so far.hold2 = Math.max(hold2, release1-i); // The maximum if we've just buy 2nd stock so far.release1 = Math.max(release1, hold1+i); // The maximum if we've just sold 1nd stock so far.hold1 = Math.max(hold1, -i); // The maximum if we've just buy 1st stock so far. }return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.}
四、 Best Time to Buy and Sell Stock IV ? ?

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

Design an algorithm to find the maximum profit. You may complete at most?k?transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

相對于前幾個問題，本問題進(jìn)行可擴(kuò)展，要求最多可以進(jìn)行k筆買賣操作。

對于k大于等于len/2的情況，該問題化為問題二的貪心；

對于k小于len/2的情況，假設(shè)我們已經(jīng)得到最大買賣筆數(shù)為k-1的問題的解，則在時刻i，假設(shè)最大買賣筆數(shù)為k的前i-1時刻的最大收益記錄在record[k][i-1]中，用currCost記錄在手中握有股票的情況下的最大收益，則最大買賣筆數(shù)為k的第i時刻的最大收益 record[k][i] = max(record[k][i-1], currCost+prices[i])，即要么為上一時刻的最大收益，要么為上一時刻持有股票情況下在時刻i買出的收益之和。對于currCost的更新，也要滿足currCost最大化，故它應(yīng)該取record[k-1][i-1]-prices[i]和currCost的較大者。

于是可以得到時間復(fù)雜度為O(k*n)，空間復(fù)雜度為O(k*n)的方法：

public int maxProfit(int k, int[] prices) {int len = prices.length;if (k >= len/2) return helper(prices);int[][] record = new int[k+1][len];for (int i = 1; i <= k; i++) {int currCost = -1*prices[0];for (int j = 1; j < len; j++) {record[i][j] = Math.max(record[i][j-1], currCost+prices[j]);currCost = Math.max(currCost, record[i-1][j-1]-prices[j]);}}return record[k][len-1];}public int helper(int[] prices) {int len = prices.length;int profit = 0;for (int i = 1; i < len; i++) {if (prices[i] > prices[i-1])profit += prices[i]-prices[i-1];}return profit;}

五、Best Time to Buy and Sell Stock with Cooldown??

Say you have an array for which the?ith?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) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]

本問題在可以進(jìn)行多次買賣操作的情況下加入了cooldown狀態(tài)，即要求賣出操作之后的第二天不能進(jìn)行買操作。

引入三個數(shù)組buy[], sell[], cooldown[]，分別記錄第i時刻進(jìn)行買、賣、保持操作所能產(chǎn)生的最大收益，可以得到如下關(guān)系：

buy[i] = max(cooldown[j]-prices[i]), j∈[0, i-1]

sell[i] = max(buy[j]+prices[i]), j∈[0, i-1]

cooldown[i] = max(sell[j]), j∈[0, i-1]

故有時間復(fù)雜度為O(n*n)，空間復(fù)雜度為O(n)的方法：

public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) return 0;int[] buy = new int[len];int[] sell = new int[len];int[] cooldown = new int[len];buy[0] = -prices[0];int ans = Integer.MIN_VALUE;for (int i = 1; i < len; i++) {buy[i] = Integer.MIN_VALUE;sell[i] = Integer.MIN_VALUE;cooldown[i] = Integer.MIN_VALUE;for (int j = 0; j < i; j++) {buy[i] = Math.max(buy[i], cooldown[j]-prices[i]);ans = Math.max(buy[i], ans);sell[i] = Math.max(sell[i], buy[j]+prices[i]);ans = Math.max(sell[i], ans);cooldown[i] = Math.max(cooldown[i], sell[j]);ans = Math.max(cooldown[i], ans);}}return ans;}
該方法可以優(yōu)化到時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)：

觀察到任意時刻總有sell[i]大于等于cooldown[i]，故不再使用cooldown數(shù)組，而是借用

buy[i] = max(buy[i-1], sell[i-2]-prices[i])

sell[i] = max(sell[i-1], buy[i-1]+prices[i])

可見buy[i]和sell[i]只依賴于i-1時刻和i-2時刻。

public int maxProfit(int[] prices) {int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;for (int price : prices) {prev_buy = buy;buy = Math.max(prev_sell - price, prev_buy);prev_sell = sell;sell = Math.max(prev_buy + price, prev_sell);}return sell;}

總結(jié)：這個系列的題不算特別難，當(dāng)然那個K次的還是比較惡心的，希望總結(jié)完以后再遇到DP的題不再那么怵了，有些人說DP的本質(zhì)不是求解遞推式，我不知道我個人的理解是否正確，最近做了一些DP的題目之后，總感覺像是一階馬爾科夫過程，有點狀態(tài)轉(zhuǎn)移方程的意思，如果理解上有了偏差，還請網(wǎng)友指正批評~

總結(jié)

以上是生活随笔為你收集整理的[LeetCode]Buy and Sell Stocks 买卖股票问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。