1 買賣股票的最佳時(shí)機(jī) V1

1.1 概述

1.1.1 題目出處

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

1.1.2 題目描述

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

如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。

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

示例 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:

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

1.2 雙指針

1.2.1 思路

雙指針，一個(gè)記錄最小股票價(jià)格，一個(gè)記錄結(jié)果。

1.2.2 代碼

class Solution {public int maxProfit(int[] prices) {int left = Integer.MAX_VALUE;int result = 0;for(int p : prices){if(p < left){// 小于左邊界，則更新左邊界left = p;} else if(p - left > result){// 利潤(rùn)大于已記錄的最大利潤(rùn)result = Math.max(result, p - left);}}return result;} }

1.2.3 時(shí)間復(fù)雜度

O(N)

1.2.4 空間復(fù)雜度

O(1)

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

1.3.1 思路

dp[i]表示前i日的最大利潤(rùn)。

則轉(zhuǎn)移方程為：
dp[i] = max( dp[i-1], prices[i] - min(prices[0 -> i]))。

也就是說，每日的最大利潤(rùn)為以下兩項(xiàng)的大者：

• 昨天的做大利潤(rùn)
• 在當(dāng)天以前的某個(gè)股價(jià)最低的一天買入股票，并在當(dāng)天賣出股票，以此賺取的利潤(rùn)

初始：
dp[0] = 0;

返回值：
dp[prices.length - 1]

1.3.2 代碼

class Solution {public int maxProfit(int[] prices) {if(prices == null || prices.length < 2){return 0;}int[] dp = new int[prices.length];dp[0] = 0;// 記錄當(dāng)天以前股價(jià)最低的一天的價(jià)格int min = prices[0];for(int i = 1; i < prices.length ; i++){dp[i] = Math.max(dp[i - 1], prices[i] - min);min = Math.min(min, prices[i]);}return dp[prices.length - 1];} }

1.3.3 時(shí)間復(fù)雜度

O(N)

1.3.4 空間復(fù)雜度

O(N)

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

1.4.1 思路

其實(shí)我們只需要記錄當(dāng)前最大利潤(rùn)，不需要記錄每一天的最大利潤(rùn)。

因?yàn)槊刻斓淖畲罄麧?rùn)肯定是不會(huì)比前面的小的。

所以只需要一個(gè)變量存最大利潤(rùn)即可，不需要dp[n]。

1.4.2 代碼

class Solution {public int maxProfit(int[] prices) {int result = 0;if(prices == null || prices.length < 2){return result;}int min = prices[0];for(int i = 1; i < prices.length ; i++){result = Math.max(result, prices[i] - min);min = Math.min(min, prices[i]);}return result;} }

1.4.3 時(shí)間復(fù)雜度

O(N)

1.4.4 空間復(fù)雜度

O(1)

2 買賣股票的最佳時(shí)機(jī) V2

2.1 概述

2.1.1 題目出處

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

2.1.2 題目描述

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

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。
隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 。
示例 2:

輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購(gòu)買股票，之后再將它們賣出。
因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購(gòu)買前出售掉之前的股票。
示例 3:

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

提示：

1 <= prices.length <= 3 * 10 ^ 4 0 <= prices[i] <= 10 ^ 4

2.2 貪心

2.2.1 思路

只要后項(xiàng)大于前項(xiàng)，則累加到結(jié)果中。
想象連續(xù)兩次漲，就累加了兩次的差值，其實(shí)就等于 第三次賣 - 第一次買的差值

其實(shí)是一個(gè)trick，沒有實(shí)際操作性，因?yàn)槟悴豢赡芴崆爸肋B續(xù)兩天的價(jià)格來決定第一天低價(jià)格買入第二天高價(jià)格賣出。

以下內(nèi)容轉(zhuǎn)自貪心算法詳解，作者 liweiwei1419

因此，

• “貪心算法” 和 “動(dòng)態(tài)規(guī)劃”、“回溯搜索” 算法一樣，完成一件事情，是分步?jīng)Q策的；
• “貪心算法” 在每一步總是做出在當(dāng)前看來最好的選擇，“最好” 的意思往往根據(jù)題目而來，可能是 “最小”，也可能是 “最大”；
• 貪心算法和動(dòng)態(tài)規(guī)劃相比，它既不看前面（也就是說它不需要從前面的狀態(tài)轉(zhuǎn)移過來），也不看后面（無后效性，后面的選擇不會(huì)對(duì)前面的選擇有影響）
  因此貪心算法時(shí)間復(fù)雜度一般是線性的，空間復(fù)雜度是常數(shù)級(jí)別的。

這道題 “貪心” 的地方在于，對(duì)于 “今天的股價(jià) - 昨天的股價(jià)”，得到的結(jié)果有 3 種可能：

• 正數(shù)
• 0
• 負(fù)數(shù)。

貪心算法的決策是：只累加正數(shù)。

2.2.2 代碼

class Solution {public int maxProfit(int[] prices) {int result = 0;if(prices.length < 2){return result;}// 只要后項(xiàng)大于前項(xiàng)，則累加到結(jié)果中。// 想象連續(xù)兩次漲，就累加了兩次的差值，其實(shí)就等于 第三次賣 - 第一次買的差值for(int i = 1; i < prices.length; i ++){if(prices[i] > prices[i-1]){result += (prices[i] - prices[i-1]);}}return result;} }

2.2.3 時(shí)間復(fù)雜度

O(N)

2.2.4 空間復(fù)雜度

O(1)

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

2.3.1 思路

可用貪心解決的一般也能用動(dòng)態(tài)規(guī)劃。

• dp[i][0]代表該天不持有股票的最大利潤(rùn)
• dp[i][1] 代表該天持有股票的最大利潤(rùn)

則轉(zhuǎn)移方程為：

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

初始：

dp[0][0] = 0; dp[0][1] = 0 - prices[0];

返回值：

// 因?yàn)樽詈笠惶毂仨毑荒艹钟泄善?#xff0c;否則肯定利潤(rùn)小于dp[prices.length - 1][0] dp[prices.length - 1][0]

2.3.2 代碼

class Solution {public int maxProfit(int[] prices) {if(prices.length < 2){return 0;}// dp[i][0]代表該天不持有股票的最大利潤(rùn)// dp[i][1] 代表該天持有股票的最大利潤(rùn)int[][] dp = new int[prices.length][2];dp[0][0] = 0;dp[0][1] = 0 - prices[0];for(int i = 1; i < prices.length; i ++){// 第二個(gè)表示 i-1日持有股票，但在i日賣出// 因?yàn)檫@暗含了加上 用 prices[i] 減去 前面買的那只股票的價(jià)格的差價(jià)dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);}return dp[prices.length - 1][0];} }

2.3.3 時(shí)間復(fù)雜度

O(N)

2.3.4 空間復(fù)雜度

O(N)

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

2.4.1 思路

最大利潤(rùn)不會(huì)減少，所以也可以用兩個(gè)變量分別記錄擁有和不擁有股票時(shí)的最大利潤(rùn)。

這樣空間復(fù)雜度降為O(N)

2.3.2 代碼

class Solution {public int maxProfit(int[] prices) {if(prices.length < 2){return 0;}int haveCost = 0 - prices[0];int notHaveCost = 0;for(int i = 1; i < prices.length; i ++){// 第二個(gè)表示 i-1日持有股票，但在i日賣出// 因?yàn)檫@暗含了加上 用 prices[i] 減去 前面買的那只股票的價(jià)格的差價(jià)notHaveCost = Math.max(notHaveCost, haveCost + prices[i]);haveCost = Math.max(haveCost, notHaveCost - prices[i]);}return notHaveCost;} }

2.4.3 時(shí)間復(fù)雜度

O(N)

2.4.4 空間復(fù)雜度

O(1)

3 最佳買賣股票時(shí)機(jī)含冷凍期

3.1 概述

3.1.1 題目出處

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

3.1.2 題目描述

給定一個(gè)整數(shù)數(shù)組，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 。?

設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤(rùn)。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。
示例:

輸入: [1,2,3,0,2]
輸出: 3
解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]

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

3.3.1 思路

考慮四種狀態(tài)的轉(zhuǎn)移圖如下：

• dp[i][0]代表該天不持有股票且非賣出的最大利潤(rùn)
  dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
• dp[i][1] 代表該天賣出股票的最大利潤(rùn)
  dp[i][1] = dp[i - 1][3] + prices[i];
• dp[i][2] 代表該天位冷凍期最大利潤(rùn)
  dp[i][2] = dp[i - 1][1];
• dp[i][3] 代表該天賣出股票的最大利潤(rùn)
  dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][0] - prices[i], dp[i-1][2] - prices[i]);

初始：

// 不持股，非賣出 dp[0][0] = 0; // 賣出 dp[0][1] = 0; // 冷凍 dp[0][2] = 0; // 持股 dp[0][3] = 0 - prices[0];

返回值：
最后結(jié)果是不持股的三種狀態(tài)的最大值

3.3.2 代碼

class Solution {public int maxProfit(int[] prices) {if(prices == null || prices.length < 2){return 0;}int[][] dp = new int[prices.length][4]; // 不持股，非賣出dp[0][0] = 0;// 賣出dp[0][1] = 0;// 冷凍dp[0][2] = 0;// 持股dp[0][3] = 0 - prices[0];for(int i = 1; i < prices.length; i++){// i日為不持股非賣出，則肯定是由i-1天不持股非賣出或冷凍轉(zhuǎn)移而來dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);// i日為賣出，則肯定是由i-1天持股且在i日賣出dp[i][1] = dp[i - 1][3] + prices[i];// i日為冷凍，則肯定是由i-1天賣出狀態(tài)轉(zhuǎn)移而來dp[i][2] = dp[i - 1][1];// i日為持股，則i-1天持股或（冷凍 || 不持股非賣出）且在i日買入持股dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][0] - prices[i]);dp[i][3] = Math.max(dp[i][3], dp[i-1][2] - prices[i]);}// 最后結(jié)果是不持股的三種狀態(tài)的最大值int result = Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);result = Math.max(result, dp[prices.length - 1][2]);return result;} }

3.3.3 時(shí)間復(fù)雜度

O(N)

3.3.4 空間復(fù)雜度

O(N)

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

3.4.1 思路

這道題目最大利潤(rùn)也是遞增，而且是只需要考慮i日和i-1日的關(guān)系，所以也已用4個(gè)變量分別記錄i日的四種狀態(tài)時(shí)的最大利潤(rùn)。

3.4.2 代碼

//TODO

3.4.3 時(shí)間復(fù)雜度

O(N)

3.4.4 空間復(fù)雜度

O(1)

4 買賣股票的最佳時(shí)機(jī) III

4.1 概述

4.1.1 題目出處

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

4.1.2 題目描述

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

4.2.1 思路

推導(dǎo)過程詳見詳細(xì)通俗的思路分析，多解法

4.2.2 代碼

class Solution {public int maxProfit(int k, int[] prices) {if (prices.length == 0) {return 0;}if (k > prices.length / 2) {// 此時(shí)，即變?yōu)榭梢匀我饨灰状螖?shù)，因?yàn)楫?dāng)天只能買或賣，直接使用貪心法求解即可return maxProfitGreedy(prices);}int K = k;int[] dp = new int[K + 1];int min[] = new int[K + 1];for (int i = 1; i <= K; i++) {min[i] = prices[0];}for (int i = 1; i < prices.length; i++) {for (int j = 1; j <= K; j++) {min[j] = Math.min(prices[i] - dp[j - 1], min[j]);dp[j] = Math.max(dp[j], prices[i] - min[j]);}}return dp[K];}public int maxProfitGreedy(int[] prices) {int result = 0;if(prices.length < 2){return result;}// 只要后項(xiàng)大于前項(xiàng)，則累加到結(jié)果中。// 想象連續(xù)兩次漲，就累加了兩次的差值，其實(shí)就等于 第三次賣 - 第一次買的差值for(int i = 1; i < prices.length; i ++){if(prices[i] > prices[i-1]){result += (prices[i] - prices[i-1]);}}return result;}

4.3 狀態(tài)機(jī)

4.3.1 思路

遍歷每個(gè)股價(jià)日，需要考慮的狀態(tài)有四個(gè)：

• 第一次買入后當(dāng)前剩余的錢
• 第一次賣出，以當(dāng)前價(jià)格的股票賣出
• 第二次買入后當(dāng)前剩余的錢
• 第二次賣出股票。

考慮四種狀態(tài)的轉(zhuǎn)移圖如下：

思路詳見 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/149383/Easy-DP-solution-using-state-machine-O(n)-time-complexity-O(1)-space-complexity

這里最關(guān)鍵的一點(diǎn)，為什么能遍歷每天時(shí)都可以用這個(gè)轉(zhuǎn)移圖去判斷，因?yàn)閷?duì)某一天來說，立刻買入又賣出的情況是無意義的，所以可以這樣轉(zhuǎn)移。也就是說，如果該天應(yīng)該買入，則只會(huì)改變s1/s3，如果當(dāng)天值得賣出，只會(huì)改變s2/s4。這是最重要的一點(diǎn)，如果想不明白的話可以把例子數(shù)值帶入，畫出每一次的幾個(gè)狀態(tài)的值就明白了。

返回值：Math.max(s4, 0) 因?yàn)閟4可能為min,即只有一個(gè)股票日時(shí)，此時(shí)就不買就行了。

4.3.2 代碼

class Solution {public int maxProfit(int[] prices) {if(prices == null || prices.length == 0) {return 0;}// 進(jìn)行初始化，第一天 s1 將股票買入，其他狀態(tài)全部初始化為最小值int s1=-prices[0], s2=Integer.MIN_VALUE, s3=Integer.MIN_VALUE, s4=Integer.MIN_VALUE;for(int i = 1; i < prices.length; i++) { s1 = Math.max(s1, 0 - prices[i]);s2 = Math.max(s2, s1 + prices[i]);s3 = Math.max(s3, s2 - prices[i]);s4 = Math.max(s4, s3 + prices[i]);}// 可能只有一個(gè)股票日，此時(shí)不買就是最佳return Math.max(0, s4);} }

4.3.3 時(shí)間復(fù)雜度

O(N)

4.3.4 空間復(fù)雜度

O(N)

參考文檔

• 貪心算法詳解
• 詳細(xì)通俗的思路分析，多解法

總結(jié)

以上是生活随笔為你收集整理的算法-贪心/动态规划-买卖股票的最佳时机的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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