问题原因分析 #

你的代码采用了暴力枚举所有可能的买卖组合的思路，虽然在小测试用例（比如你给出的[7,1,5,3,6,4]）中能正常运行，但当LeetCode使用超大长度的prices数组测试时，tmp数组会存储n*(n-1)/2个元素——比如当n=10^4时，这个数组就有近5000万条数据，直接超出了Node.js堆内存的限制，所以触发了allocation failure GC in old space requested的内存溢出错误。

优化后的解决方案 #

我们可以把空间复杂度从O(n²)降到O(1)，只需要一次遍历，记录当前遇到的最低价格和当前能获得的最大利润即可：

var maxProfit = function(prices) {
    if (prices.length <= 1) return 0;
    let minPrice = prices[0];
    let maxProfit = 0;
    for (let i = 1; i < prices.length; i++) {
        // 如果当前价格比记录的最低价格还低，更新最低价格
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            // 计算当前卖出的利润，和当前最大利润比较并更新
            const currentProfit = prices[i] - minPrice;
            if (currentProfit > maxProfit) {
                maxProfit = currentProfit;
            }
        }
    }
    return maxProfit;
};

// 测试用例
console.log(maxProfit([7,1,5,3,6,4])); // 输出5

优化思路说明 #

• 初始化minPrice为数组第一个元素，maxProfit为0（因为如果所有价格都下跌，最佳选择是不交易，利润为0）。
• 从第二个元素开始遍历数组：
  • 若当前价格比minPrice低，说明找到更优的买入点，更新minPrice。
  • 否则，计算当前价格卖出的利润，若这个利润比maxProfit大，就更新maxProfit。
• 遍历结束后返回maxProfit，全程不需要额外存储大量利润数据，完美解决内存溢出问题。

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