Leetcode 121买卖股票最佳时机暴力解法内存超限问题排查求助

核心问题点 #

• 你额外创建了profit数组存储所有的买卖差值，这个数组的空间复杂度为O(n²)。当输入的prices数组长度较大时（比如LeetCode常见的1e5级别测试用例），需要存储的差值总量为n*(n-1)/2，1e5长度的输入会产生接近50亿条差值记录，直接超出内存限制。
• 存储所有差值的操作完全是冗余的：你最终需要的只是所有差值中的最大值，不需要保留所有差值的历史记录，完全可以在遍历计算的过程中实时更新最大利润，省略存储所有差值的步骤。

优化后的暴力解法（解决内存超限问题） #

from typing import List
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        n = len(prices)
        if n <= 1:
            return 0
        for i in range(n):
            for j in range(i+1, n):
                current_profit = prices[j] - prices[i]
                if current_profit > max_profit:
                    max_profit = current_profit
        return max_profit

修改后的代码空间复杂度降到O(1)，不会再触发内存超限，但时间复杂度仍为O(n²)，面对大长度测试用例时会触发时间超限。

进一步优化方向 #

可以只遍历一次数组，实时维护当前位置之前的最小价格，计算当前价格减去最小价格的利润，同步更新最大利润即可，时间复杂度降到O(n)，空间复杂度保持O(1)，可以通过所有测试用例。

排查思路参考 #

遇到内存限错时优先排查额外开辟的存储结构的空间复杂度，确认是否存在和输入规模成平方/指数级增长的存储内容，再判断这些存储内容是否有必要存在，能不能通过实时计算、实时更新结果的方式省略冗余存储。

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