LeetCode 121：买卖股票的最佳时机暴力解法优化问题

解决越界+优化暴力法的思路 #

要避免prices[z+1]数组越界，直接把外层循环的遍历范围限制在数组的倒数第二个元素之前就行——也就是让z只走到len(prices)-2，这样z+1最多就是数组最后一个索引，绝对不会越界。

至于你想加的判断逻辑完全成立：如果当天价格prices[z]比第二天prices[z+1]还高，那在z天买入肯定不如等z+1天买——毕竟z+1天价格更低，后续不管什么时候卖出，利润只会更高（或亏损更少），这种情况直接跳过z天的内层循环就行，没必要做无用计算。

优化后的代码示例（Python） #

def maxProfit(prices):
    max_profit = 0
    n = len(prices)
    # 外层循环只到倒数第二个元素，避免z+1越界
    for z in range(n - 1):
        # 当前价比下一天高，直接跳过内层循环
        if prices[z] > prices[z+1]:
            continue
        # 计算后续所有卖出可能的利润，更新最大值
        for j in range(z + 1, n):
            profit = prices[j] - prices[z]
            if profit > max_profit:
                max_profit = profit
    return max_profit

针对长降序数组（比如[10000,9999,...,0]），每个z都会触发跳过判断，外层循环只走O(n)次，完全不会超时。

更高效的O(n)解法（推荐） #

其实还有比优化暴力法更高效的思路：只遍历一次数组，记录当前遇到的最低买入价，同时计算当天卖出的利润，实时更新最大利润。代码如下：

def maxProfit(prices):
    if not prices:
        return 0
    min_price = prices[0]
    max_profit = 0
    for price in prices[1:]:
        # 更新当前最低买入价
        if price < min_price:
            min_price = price
        # 计算当天卖出的利润，更新最大值
        else:
            profit = price - min_price
            if profit > max_profit:
                max_profit = profit
    return max_profit

这个方法不管数组规模多大，都只走一次遍历，时间复杂度稳定在O(n)，彻底解决超时问题。

内容的提问来源于stack exchange，提问作者Itay86