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

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

✨核心逻辑

本题采用 贪心算法 的策略:

  1. 拆解利润:由于不限制交易次数(且同一时间只能持有一股),我们可以把一段时间的上涨利润拆解成每天的“小利润”。比如 1 -> 2 -> 3 的总利润为 2,等同于 (2-1) + (3-2)
  2. 只要涨就赚:遍历数组,比较 今天昨天 的价格。
  3. 差价累加:只要今天的价格比昨天高,说明昨天买今天卖就能赚到这笔差价,直接将其累加到总利润中。
  4. 下跌不操作:如果今天价格比昨天低,就不做买卖操作,避免亏损。
  5. 最终收益:累加完所有上涨日的差值,就是能够获取的最大利润。

🔥代码实现(含详细变量注释)

class Solution {
    public int maxProfit(int[] prices) {
        // maxProfit:记录最终能获取到的最大总利润,初始为0
        int maxProfit = 0;
        
        // i:遍历指针,从索引 1(即数组的第二天)开始遍历,我们需要对比今天和昨天的价格
        for (int i = 1; i < prices.length; i++) {
            // 核心判断:如果今天的价格高于昨天的价格,说明有上涨空间,可以获利
            if (prices[i] > prices[i - 1]) {
                // 获取当天的差价利润,并累加到总利润变量 maxProfit 中
                // 等价于:昨天买,今天卖,赚取这一天的差价
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        
        // 遍历完成后,返回累加计算出的最大总利润
        return maxProfit;
    }
}
  • ⏱️复杂度分析
    • 时间复杂度:O(N),其中 N 是数组的长度。代码只进行一次遍历,在循环内部执行常数次操作

    • 空间复杂度:O(1),仅用到 maxProfit 和 i 两个额外的整型变量,没有使用额外的数组空间。

🔍反思一下:

起初思路很乱无从下手:每一天都可以卖出股票同时也可以买入,无法决定什么时候买入和卖出,可变因素很多

题目里的隐藏条件:你可以同一天卖出,再同一天买入。

因此不要去思考“买和卖”,把思维转变为:“只要今天的价格比昨天高,我就当自己昨天买入了,今天卖出了,钱直接放进口袋。”


📚此图利于理解

image-MNxJ.png