手帐 Blog

主题

复盘 · LC 121 买卖股票的最佳时机 ​

题目 ​

题意 ​

给定数组 prices，prices[i] 是第 i 天股票价格。你最多完成一笔交易（先买后卖），求能获得的最大利润；不能赚钱则返回 0。

  • 必须先买后卖（卖出下标 > 买入下标）。
  • 约束常见：1 <= prices.length <= 10^5，0 <= prices[i] <= 10^4。

边界：单日、全程下跌、最低价在最后、最高价在最前。

涉及算法 ​

标签一句话
一次遍历 / 贪心维护「至今最低买入价」，每天算卖出利润取 max
一维 DP 视角dp[i] = 前 i 天最大利润；或「持有/未持有」状态压缩

教程对照：一维状态意识可看 21 · DP 入门 · 一维；本题本质是数组一次扫描。

评价我的解法 ​

想法是：维护当前 min/max 及下标；发现新低就清空 max；发现新高就 push(max - min)；最后对差值数组取 Math.max。方向对——「低点之后找高点」——但实现偏绕。

我的代码（摘自 121-买卖股票的最佳时机/index.js，不含本地测例与调试 console.log）：

javascript
var maxProfit = function (prices) {
  const MAX = 10000;
  const MIN = 0;
  let min = MAX;
  let max = MIN;
  let minP = -1;
  let maxP = -1;
  let resArr = [];
  for (let i = 0; i < prices.length; i++) {
    const item = prices[i];

    if (minP !== -1 && i > minP && item > min && (maxP === -1 || item > max)) {
      max = item;
      maxP = i;
      resArr.push(max - min);
    }
    if (item < min) {
      min = item;
      minP = i;
      max = MIN;
      maxP = -1;
    }
  }
  if (resArr.length === 0) {
    return 0;
  }
  return Math.max(...resArr);
};
  • 正确性：在题目价格上界 10^4 下，多数用例（含 [2,4,1]、[7,1,5,3,6,4]）能算出对的最大差；MAX = 10000 当初值，首日恰为 10000 时靠「后面不可能更高」碰巧不炸。
  • 问题：
    1. 状态过多：minP/maxP/resArr 都不是必要；只要「历史最低价 + 当前利润」即可。
    2. Math.max(...resArr) 在 n 很大时有参数展开风险；且 resArr 额外 O(n) 空间。
    3. MAX = 10000 应写成 Infinity（或直接用 prices[0]），别绑死题面常量。
    4. 提交前应去掉调试 console.log。

小结：能过 Easy，但复杂度意识和代码简洁度弱——这题正是练「一次遍历维护最优」的好题。

最佳题解 ​

一次遍历，维护最低价与最大利润：

javascript
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let minPrice = Infinity;
  let best = 0;
  for (const p of prices) {
    if (p < minPrice) minPrice = p;
    else best = Math.max(best, p - minPrice);
  }
  return best;
};
  • 时间 O(n)，空间 O(1)。
  • 为何更优：每个价格常数次比较；不存候选差分数组；边界（无利润、单日）自然落成 0。

关联题目 ​

题为何相关
122. 买卖股票的最佳时机 II可多次买卖；贪心累加上涨段
123. 买卖股票的最佳时机 III最多两笔，状态机 DP
53. 最大子数组和「前缀最优」同族一次扫描手感

一句话带走 ​

只买卖一次：扫一遍，记历史最低价，用当天价减它更新最大利润。