如何将计算股票最大收益的函数时间复杂度优化至O(n)

核心思路 #

完全存在时间复杂度为O(n)的最优解法，核心逻辑非常简单：

• 对于任意卖出日期来说，能拿到的最高收益，等于当天价格减去该日期之前的历史最低买入价
• 遍历过程只需要维护两个变量即可：
  • minPrice：记录遍历到当前位置之前的最低买入价格
  • maxProfit：记录当前计算得到的最高收益
• 整体仅需遍历数组1次，时间复杂度为O(n)，空间复杂度为O(1)，相比你原有的O(n²)暴力解法，在长序列价格计算场景下效率提升非常明显。

逻辑对齐说明 #

以下实现和你现有代码的逻辑完全一致：

• 允许收益为负（价格持续下跌时返回最小亏损值）
• 兼容空数组、长度为1的数组等边界输入

Java实现代码 #

public static int getResult(int[] array) {
    // 边界输入处理
    if (array == null || array.length == 0) {
        return Integer.MIN_VALUE;
    }
    if (array.length == 1) {
        return 0;
    }
    int minPrice = array[0];
    int maxProfit = Integer.MIN_VALUE;
    for (int i = 1; i < array.length; i++) {
        // 计算当日卖出可获得的收益
        int currentProfit = array[i] - minPrice;
        // 更新最大收益
        if (currentProfit > maxProfit) {
            maxProfit = currentProfit;
        }
        // 更新历史最低价格，供后续日期计算使用
        if (array[i] < minPrice) {
            minPrice = array[i];
        }
    }
    return maxProfit;
}

效果验证 #

举个例子，输入价格数组[7,1,5,3,6,4]：

• 遍历到下标1（价格1）时更新历史最低价为1
• 遍历到下标4（价格6）时计算收益为6-1=5，为全局最大收益，最终返回值和暴力解法计算结果完全一致。

内容的提问来源于stack exchange，提问作者Enes Körhan