文章目錄

• • Leetcode 121. 買賣股票的最佳時機
  • Leetcode 122.買賣股票的最佳時機II

Leetcode 121. 買賣股票的最佳時機

題目鏈接： Leetcode 121. 買賣股票的最佳時機
題目描述： 給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。你只能選擇某一天買入這只股票，并選擇在未來的某一個不同的日子賣出該股票。設計一個算法來計算你所能獲取的最大利潤。返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。
思路： 本題可以用貪心來做，貪心策略：在最便宜的一天買入，然后在該天之后最高的一天（不一定是所有元素最大值）賣出。
代碼如下：（貪心）

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]);             // 維護最小值result = max(result, prices[i] - low); // 求最大收益}return result;}
};

• 時間復雜度：$O(n)$
• 空間復雜度：$O(1)$

貪心的做法關鍵在于想到合適的貪心策略。如果沒想到貪心策略，本題也可以通過動態規劃來解決：

• dp[i][0]： 表示第i天持有股票所得最多現金；dp[i][1] 表示第i天不持有股票所得最多現金
• 遞推公式： 如果第i天持有股票，則有dp[i][0] = max(dp[i - 1][0], -prices[i])；如果第i天不持有股票，則有dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])
• 初始化： dp[0][0] = -prices[0] ，dp[0][1] = 0
• 遍歷順序：從前向后遍歷

代碼如下：（dp）

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2));// dp[i][0]代表第i天持有股票；dp[i][1]代表第i天不持有股票dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < n; 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]);}return dp[n - 1][1]; // 無論如何最后都要賣出股票}
};

• 時間復雜度：$O(n)$
• 空間復雜度：$O(n)$

我們根據遞推公式發現，dp[i]只取決于dp[i - 1]的狀態，因此只需要大小為2的數組即可。
代碼如下：（dp+滾動數組優化）

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(2, vector<int>(2));// dp[i][0]代表第i天持有股票；dp[i][1]代表第i天不持有股票dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < n; i++) {dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]);dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);}return dp[(n - 1) % 2][1]; // 無論如何最后都要賣出股票}
};

• 時間復雜度：$O(n)$
• 空間復雜度：$O(1)$

Leetcode 122.買賣股票的最佳時機II

題目鏈接： Leetcode 122.買賣股票的最佳時機II
題目描述： 給你一個整數數組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。在每一天，你可以決定是否購買或出售股票。你在任何時候最多只能持有一股股票。你也可以先購買，然后在同一天出售。返回你能獲得的最大利潤 。
思路： 本題我之前用貪心實現過：可以看這里，因此這里主要介紹動態規劃的做法。

本題與上道題的動態規劃思路基本相同，唯一的區別在于：由于可以多次買賣股票，因此推導dp[i][0]時，需要考慮第i天買入股票的情況，單純用-prices[i]表示就不可以了。

• dp[i][0]： 表示第i天持有股票所得最多現金；dp[i][1] 表示第i天不持有股票所得最多現金
• 遞推公式： 如果第i天持有股票，則有dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])；如果第i天不持有股票，則有dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])
• 初始化： dp[0][0] = -prices[0] ，dp[0][1] = 0
• 遍歷順序：從前向后遍歷

代碼如下：（dp）

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2));// dp[i][0]代表第i天持有股票；dp[i][1]代表第i天不持有股票dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < n; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//與121的唯一區別dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[n - 1][1];}
};

• 時間復雜度：$O(n)$
• 空間復雜度：$O(n)$

代碼如下：（dp+滾動數組優化）

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(2, vector<int>(2));// dp[i][0]代表第i天持有股票；dp[i][1]代表第i天不持有股票dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < n; i++) {dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);}return dp[(n - 1) % 2][1];}
};

• 時間復雜度：$O(n)$
• 空間復雜度：$O(1)$

---

總結： 這兩道題不算難，不過需要理解好兩道題的遞推公式，不僅要知其然，還要知其所以然。

最后，如果文章有錯誤，請在評論區或私信指出，讓我們共同進步！