leetcode 122 买卖股票的最佳时机II

傷城~ 2022-08-28 07:48 156阅读 0赞

## 前言 ##

题目：[122. 买卖股票的最佳时机 II][122. _ II]

参考题解：[买卖股票的最佳时机 II-代码随想录][II-]

## 提交代码 ##

因为之前做过[leetcode 376 摆动序列][leetcode 376]，所以很自然想到，使用贪心策略，累加求和所有的上坡(局部谷底->局部峰值)差值。

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            // 贪心策略：在波动的低估买入，峰值卖出
            // 策略证明：不放过每个赚钱的机会
            int result = 0;
            int low,high;
            for(int i=0; i<prices.size()-1; i++){
                if(prices[i+1] > prices[i]){ // 在上坡
                    low = i;
                    while(i<prices.size()-1 && prices[i+1] > prices[i]) // 循环退出时，i在当前坡的峰值
                        i++;
                    high = i;
                    result += (prices[high] - prices[low]);
                }
            }
    
            return result;
        }
    };

上面的贪心策略，等价于“局部最优：收集每天的正利润，全局最优：求得最大利润”。

下面代码来自参考题解。

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int result = 0;
            for (int i = 1; i < prices.size(); i++) {
                result += max(prices[i] - prices[i - 1], 0);
            }
            return result;
        }
    };

[122. _ II]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
[II-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.md
[leetcode 376]: https://blog.csdn.net/sinat_38816924/article/details/120605436