贪心与堆简单1 种解法

#121买卖股票的最佳时机

只允许完成一笔先买后卖的交易，求可获得的最大利润。

#数组#贪心#股票

解题主线

把当天视为卖出日时，最优买入价一定是此前出现过的最低价格。

扫描顺序天然保证先买后卖；先更新最低价再计算利润也不会产生非法收益。

解法 1：维护历史最低价

从左到右维护历史最低买入价，并用当天价格减去该最低价更新最大利润。

时间复杂度

O(n)

空间复杂度

O(1)

121. 买卖股票的最佳时机 · 维护历史最低价

java

final class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        return maxProfit;
    }
}

从左到右维护历史最低买入价，并用当天价格减去该最低价更新最大利润。

边界与易错点

不能用全局最小值和全局最大值直接相减，因为最大值可能出现在最小值之前。
价格持续下跌时应返回 0，表示不交易。
旧源码两个方法只是循环写法不同，算法完全同构，因此只保留一种。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/greedy/Q121_maxStockProfit.java