LeetCode - Best Time to Buy and Sell Stock Series

Easy Medium Hard

121. Best Time to Buy and Sell Stock 122. Best Time to Buy and Sell Stock II 123. Best Time to Buy and Sell Stock III 188. Best Time to Buy and Sell Stock IV

121. Best Time to Buy and Sell Stock

題目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 price = 1 and sell on day 5 price = 6, profit = 6 - 1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints

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

解題思路

這題只能做一次交易
也就是只能買一次、賣一次

狀態定義：
- buy：目前為止，買入股票後的最大收益
- sell：目前為止，賣出股票後的最大收益
對每一天的 price
- 更新買入狀態：
  - buy = max(buy, -price)
  - 代表選擇在目前這天買，或是維持之前比較好的買入狀態
- 更新賣出狀態：
  - sell = max(sell, price + buy)
  - 代表選擇在目前這天賣，或是維持之前比較好的賣出狀態
最後答案為：
sell

Solution Code

Time Complexity
O(n)

Space Complexity
O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN, sell = INT_MIN;
        for(int price: prices){
            buy = max(buy, -price);
            sell = max(sell, price + buy);
        }
        return sell;
    }
};

122. Best Time to Buy and Sell Stock II

題目

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock.

Find and return the maximum profit you can achieve.

Example 1

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 price = 1 and sell on day 3 price = 5, profit = 5 - 1 = 4.
Then buy on day 4 price = 3 and sell on day 5 price = 6, profit = 6 - 3 = 3.
Total profit is 4 + 3 = 7.

Example 2

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 price = 1 and sell on day 5 price = 5, profit = 5 - 1 = 4.
Total profit is 4.

Example 3

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints

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

解題思路

這題可以做無限次交易
只要不會同時持有超過一股股票即可

因為可以多次買賣
- 只要今天比昨天貴，就可以賺這段差價
對每一天 i
- 如果 prices[i] > prices[i-1]
  - 就把差價加進答案
    ans += prices[i] - prices[i-1]
這樣等價於把所有上漲區間的利潤全部吃下來
最後答案為：
ans

Solution Code

Time Complexity
O(n)

Space Complexity
O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); ++i){
            if(prices[i] > prices[i-1]) ans += prices[i] - prices[i-1]; // 只要今天比昨天貴，就賺差價
        }
        return ans;
    }
};

123. Best Time to Buy and Sell Stock III

題目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously, i.e., you must sell the stock before you buy again.

Example 1

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 price = 0 and sell on day 6 price = 3, profit = 3 - 0 = 3.
Then buy on day 7 price = 1 and sell on day 8 price = 4, profit = 4 - 1 = 3.

Example 2

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 price = 1 and sell on day 5 price = 5, profit = 5 - 1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3

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

Constraints

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5

解題思路

這題最多可以做兩次交易
可以拆成四個狀態來更新

狀態定義：
- buy1：第一次買入後的最大收益
- sell1：第一次賣出後的最大收益
- buy2：第二次買入後的最大收益
- sell2：第二次賣出後的最大收益
對每一天的 price，依序更新：
- 第一次買：
  - buy1 = max(buy1, -price)
- 第一次賣：
  - sell1 = max(sell1, price + buy1)
- 第二次買：
  - buy2 = max(buy2, sell1 - price)
  - 可行因為題目沒規定不能當天買當天售出
- 第二次賣：
  - sell2 = max(sell2, price + buy2)
最後答案為：
sell2

Solution Code

Time Complexity
O(n)

Space Complexity
O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        
        int buy1 = INT_MIN, sell1 = INT_MIN, buy2 = INT_MIN, sell2 = INT_MIN;
        for(auto price: prices){ // O(n) 更新 DP
            buy1 = max(buy1, -price);
            sell1 = max(sell1, price + buy1);
            buy2 = max(buy2, sell1 - price); // 可行因為題目沒規定不能當天買當天售出
            sell2 = max(sell2, price + buy2);
        }
        return sell2;
    }
};

188. Best Time to Buy and Sell Stock IV

題目

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously, i.e., you must sell the stock before you buy again.

Example 1

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 price = 2 and sell on day 2 price = 4, profit = 4 - 2 = 2.

Example 2

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 price = 2 and sell on day 3 price = 6, profit = 6 - 2 = 4.
Then buy on day 5 price = 0 and sell on day 6 price = 3, profit = 3 - 0 = 3.

Constraints

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

解題思路

這題最多可以做 k 次交易
是 123. Best Time to Buy and Sell Stock III 的一般化版本

如果 k >= n / 2
- 代表交易次數幾乎沒有限制
- 可以直接當作 122. Best Time to Buy and Sell Stock II
- 只要今天比昨天貴，就賺差價
否則使用 DP：
- buy[j]：做完第 j 次買入後的最大收益
- sell[j]：做完第 j 次賣出後的最大收益
初始化：
- buy 初始化為 INT_MIN
- sell 初始化為 0
- buy[0] = 0
- sell[0] = 0
對每一天的 price
- 枚舉第 j 次交易
做第 j 次買：
- buy[j] 不買
- sell[j-1] - price 今天買
- 代表先完成 j-1 次交易，然後用這些錢買股票
- 因此：
  buy[j] = max(buy[j], sell[j-1] - price)
做第 j 次賣：
- sell[j] 不賣
- buy[j] + price 今天賣
- 代表之前已經做完第 j 次買，現在把股票賣掉
- 因此：
  sell[j] = max(sell[j], buy[j] + price)
最後答案為：
sell[k]

Solution Code

Time Complexity
O(n × k)

Space Complexity
O(k)

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(k >= n/2){ // k >= n/2，就可以直接看比前一天賺錢就賣
            int ans = 0;
            for(int i = 1; i < n; ++i){
                if(prices[i] > prices[i-1]) ans += prices[i] - prices[i-1];
            }
            return ans;
        }

        vector<int> buy(k+1, INT_MIN);
        vector<int> sell(k+1, 0);

        buy[0] = 0;
        sell[0] = 0;
        for(auto price: prices){
            for(int j = 1; j <= k; ++j){ // 做第 j 次買賣
                // 做第 j 次買: 
                // buy[j] 不買
                // sell[j-1] - price 今天買 (先完成 j-1 次交易（sell[j-1]), 然後用這些錢買股票（-price）)
                buy[j] = max(buy[j], sell[j-1] - price);

                // 做第 j 次賣: 
                // sell[j] 不賣
                // buy[j-1] + price 今天買 我之前已經做完第 j 次買（buy[j]）, 現在把股票賣掉（+price）)
                sell[j] = max(sell[j], buy[j] + price);
            }
        }
        return sell[k];
    }
};

Conclusion

這四題其實是同一個股票買賣 DP 系列，只是限制條件逐漸放寬或一般化

1. Best Time to Buy and Sell Stock
- 簡單 DP
- 只能做一次交易
- 維護 buy 和 sell
- 本質是找最低買點與最高賣點
1. Best Time to Buy and Sell Stock II
- 直接 Greedy
- 可以做無限次交易
- 只要今天比昨天貴，就直接賺差價
- 本質是吃下所有上升區間
1. Best Time to Buy and Sell Stock III
- 壓縮 DP
- 最多做兩次交易
- 維護 buy1、sell1、buy2、sell2
- 本質是把一次交易 DP 擴展成兩次交易 DP
1. Best Time to Buy and Sell Stock IV
- 泛化 DP
- 最多做 k 次交易
- 使用 buy[j] 和 sell[j]
- 本質是 123 的一般化版本
- 如果 k >= n / 2，就退化成 122 的無限次交易情況