【經典】買賣股票的最佳時機（多次交易）

一、題目

力扣原題：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

二、峰谷法

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        int i = 0;
        while (i < prices.length - 1) {
            // 找到下一個谷
            while (i < prices.length - 1 && prices[i] >= prices[i + 1]) {
                i++;
            }
            int low = prices[i];

            // 找到下一個峰
            while (i < prices.length - 1 && prices[i] < prices[i + 1]) {
                i++;
            }
            int high = prices[i];

            result = result + (high - low);
        }
        return result;
    }
}
           

• 基本思路：通過股票價格的折線圖，可以知道若想達到收益的最大化，不能錯過每一段上升的曲線。在每段上升曲線的最低處購入股票，并在最高處出售股票即可。
• 時間複雜度：O(n)。周遊一次數組即可。
• 空間複雜度：O(1)

三、貪心算法

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            // 隻要比前一天不是負增長，就可以算入收益
            result = result + Math.max(0, prices[i] - prices[i - 1]);
        }
        return result;
    }
}
           

• 基本思路：這個問題可以等價于每天都進行股票買賣，隻要當天股票價格不是負增長，便可以出手。每一天的決策都是當下最好的決定，展現了貪心的思想。
• 時間複雜度：O(n)
• 空間複雜度：O(1)

四、總結

• 峰谷法的關鍵在于畫出折線圖，折線圖一出，一切就明朗了；
• 收益最大化的問題經常可以采用貪心算法；
• 本題也可以通過暴力、DP解答，但比較複雜，後續有時間再補充吧；