122. 买卖股票的最佳时机 II
✨核心逻辑
本题采用 贪心算法 的策略:
- 拆解利润:由于不限制交易次数(且同一时间只能持有一股),我们可以把一段时间的上涨利润拆解成每天的“小利润”。比如
1 -> 2 -> 3的总利润为2,等同于(2-1) + (3-2)。 - 只要涨就赚:遍历数组,比较 今天 和 昨天 的价格。
- 差价累加:只要今天的价格比昨天高,说明昨天买今天卖就能赚到这笔差价,直接将其累加到总利润中。
- 下跌不操作:如果今天价格比昨天低,就不做买卖操作,避免亏损。
- 最终收益:累加完所有上涨日的差值,就是能够获取的最大利润。
🔥代码实现(含详细变量注释)
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 两个额外的整型变量,没有使用额外的数组空间。
🔍反思一下:
起初思路很乱无从下手:每一天都可以卖出股票同时也可以买入,无法决定什么时候买入和卖出,可变因素很多
题目里的隐藏条件:你可以同一天卖出,再同一天买入。
因此不要去思考“买和卖”,把思维转变为:“只要今天的价格比昨天高,我就当自己昨天买入了,今天卖出了,钱直接放进口袋。”
📚此图利于理解
