LeetCode刷题复盘笔记—一文搞懂贪心算法之122. 买卖股票的最佳时机 II问题（贪心算法系列第三篇）

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

今日主要总结一下可以使用贪心算法解决的一道题目122. 买卖股票的最佳时机 II

题目122. 买卖股票的最佳时机 II

Leetcode题目地址
题目描述
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。

在每一天你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买然后在同一天出售。

返回你能获得的最大利润。

示例 1

输入prices = [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 = 1的时候买入在第 3 天股票价格 = 5的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后在第 4 天股票价格 = 3的时候买入在第 5 天股票价格 = 6的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2

输入prices = [1,2,3,4,5]
输出4
解释在第 1 天股票价格 = 1的时候买入在第 5 天股票价格 = 5的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3

输入prices = [7,6,4,3,1]
输出0
解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为 0 。

提示

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

本题重难点

这道题之前用动态规划算法进行过详细讲解一文搞懂动态规划之122. 买卖股票的最佳时机 II问题同时这道题还可以使用贪心算法解决

本题首先要清楚两点

只有一只股票
当前只有买股票或者卖股票的操作
想获得利润至少要两天为一个交易单元。

贪心算法思路这道题目可能我们只会想选一个低的买入再选个高的卖再选一个低的买入…循环反复。

如果想到其实最终利润是可以分解的那么本题就很容易了

如何分解呢

假如第0天买入第3天卖出那么利润为prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度而不是从0天到第3天整体去考虑

那么根据prices可以得到每天的利润序列(prices[i] - prices[i - 1])…(prices[1] - prices[0])。

如图

一些同学陷入第一天怎么就没有利润呢第一天到底算不算的困惑中。

第一天当然没有利润至少要第二天才会有利润所以利润的序列比股票序列少一天

从图中可以发现其实我们需要收集每天的正利润就可以收集正利润的区间就是股票买卖的区间而我们只需要关注最终利润不需要记录区间。

那么只收集正利润就是贪心所贪的地方

局部最优收集每天的正利润全局最优求得最大利润。

局部最优可以推出全局最优找不出反例试一试贪心

C++代码

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