当前位置：首页 > news >正文

力扣（买卖股票的最佳时机I/II）

news 2025/8/11 13:52:31

一、引言

在 LeetCode 中，买卖股票的最佳时机系列题目是经典的数组算法应用问题，主要考查对贪心算法等思想的理解与运用。本文将针对 121. 买卖股票的最佳时机 和 122. 买卖股票的最佳时机 II 两道题目，详细讲解解题思路、算法思想，并结合代码注释深入分析实现过程。

二、买卖股票的最佳时机 I

（一）题目分析

给定股票价格数组 prices，要求在只能进行一次 “买入 - 卖出” 操作（买入在前、卖出在后，且日期不同）的情况下，计算能获取的最大利润；若无法获利，返回 0 。核心是找到买入价格最低的时机，再在后续找到卖出价格最高且能保证盈利的时机。

（二）算法思想：贪心算法

贪心算法的核心是在每一步选择中都采取当前状态下最优的选择，从而希望最终得到全局最优解。对于本题，我们的贪心策略是：持续维护当前遇到的最低股票价格 minPrice，并在遍历数组过程中，不断计算当前价格与最低价格的差值，更新最大利润 maxProfit 。因为要获得最大利润，理论上应在价格最低时买入，之后价格最高时卖出（且卖出在买入之后），通过遍历一次数组，就能确定这个最优情况。

（三）代码实现及注释

class Solution {public int maxProfit(int[] prices) {// 初始化最低价格为整数最大值，确保第一次遇到的股票价格能更新它int minPrice = Integer.MAX_VALUE; // 初始化最大利润为 0，若无法获利就返回此默认值int maxProfit = 0; // 遍历股票价格数组for (int i = 0; i < prices.length; i++) { if (prices[i] <= minPrice) { // 遇到更低价格，更新最低价格minPrice = prices[i]; } else { // 若当前价格高于最低价格，计算可能的利润并更新最大利润maxProfit = Math.max(maxProfit, prices[i] - minPrice); }}return maxProfit;}
}

（四）逻辑流程

初始化 minPrice 为极大值、maxProfit 为 0 。
遍历数组：
- 若当前价格小于等于 minPrice，更新 minPrice 为当前价格，代表找到更优的买入时机。
- 若当前价格大于 minPrice，计算当前价格与 minPrice 的差值，用 Math.max 函数比较该差值和 maxProfit，取较大值更新 maxProfit，代表找到更优的卖出时机，能获得更大利润。
遍历结束后，maxProfit 就是一次交易能获得的最大利润，返回即可。

三、买卖股票的最佳时机 II

（一）题目分析

与买卖股票的最佳时机 I不同，本题允许在股票价格波动过程中进行多次 “买入 - 卖出” 操作（同一天可先买后卖），但任何时刻最多持有一股股票，目标是计算多次交易后能获得的最大总利润。需要抓住每次价格上涨的机会，实现 “低买高卖” 来累加利润。

（二）算法思想：贪心算法

同样运用贪心策略，不过这里的贪心逻辑是：只要后一天的股票价格高于前一天，就进行交易（前一天买入、后一天卖出），把每次价格上涨带来的利润累加起来 。因为可以多次交易，所以每次遇到价格上升的情况，都抓住 “差价” 获利，这样累加后的总利润就是能获得的最大利润。这是因为每次小的盈利累积起来，最终结果等价于找到所有价格上升区间并进行交易的总收益，能保证全局最优。

（三）代码实现及注释

class Solution {public int maxProfit(int[] prices) {// 初始化总利润为 0int sumPrices = 0; // 初始化当前持有的最低价格（初始为第一天价格）int min = prices[0]; // 从第二天开始遍历价格数组for (int len = 1; len < prices.length; len++) { // 若当前价格高于之前持有的最低价格，说明有盈利空间if (prices[len] > min) { // 累加此次交易的利润（当前价格 - 之前最低价格）sumPrices += prices[len] - min; // 卖出后，更新当前持有的最低价格为当前价格（相当于完成一次买卖，重新开始找下一次机会）min = prices[len]; }// 若当前价格低于之前持有的最低价格，更新最低价格，准备后续可能的买入if (min > prices[len]) { min = prices[len]; }}return sumPrices;}
}

（四）逻辑流程

初始化总利润 sumPrices 为 0，初始持有最低价格 min 为数组第一个元素（相当于第一天买入）。
从数组第二个元素开始遍历：
- 当 prices[len] > min 时，说明能盈利，把利润（prices[len] - min ）累加到 sumPrices ；同时更新 min 为当前价格 prices[len]，模拟完成一次 “卖出 - 重新买入” 操作（因为要继续找后续可能的盈利机会）。
- 当 min > prices[len] 时，说明当前价格更低，更新 min 为 prices[len]，相当于调整了买入时机，准备在后续价格上涨时获利。
遍历结束后，sumPrices 就是多次交易后能获得的最大总利润，返回该值。

四、总结

买卖股票的最佳时机：利用贪心算法维护最低买入价，单次遍历数组计算最大利润，时间复杂度为 $O (n)$ （ $n$ 是数组长度），空间复杂度为 $O (1)$ （只用到常数级额外空间）。通过一次遍历就能确定最优的 “单次买卖” 时机，高效解决问题。
买卖股票的最佳时机II：同样基于贪心算法，抓住每次价格上涨的微小盈利机会，累加得到总利润。时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。通过不断调整 “虚拟买入 - 卖出” 操作，充分利用价格波动获取最大收益。