贪心的经典应用

买卖股票的最佳时机如何贪心求解？

• 单次交易: 遍历时同时维护历史最低价与最大利润;
• 贪心选择性质: 以当天为卖出日时, 最优买点必然是之前的最低价;
• 最优子结构: 到第 $i$ 天的最大利润只依赖前 $i-1$ 天的最低价;

const maxProfit = (prices) => {
  let min = prices[0];
  let max = 0;
  for (let i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i]); // 更新历史最低价
    max = Math.max(max, prices[i] - min); // 以当天卖出
  }
  return max;
};

• 复杂度: 时间 $O(n)$, 空间 $O(1)$;
• 多次交易: 只要当天价格高于前一天就累加差值, 等价于吃掉每一段上涨;

const maxProfitII = (prices) => {
  let res = 0;
  for (let i = 1; i < prices.length; i++) res += Math.max(0, prices[i] - prices[i - 1]);
  return res;
};

跳跃游戏如何贪心求解？

• 目标: 用最少跳跃次数到达数组末尾;
• 贪心选择性质: 在当前能到达的区间内, 选择能使下一步覆盖最远的落点;
• 实现: 维护当前跳跃的边界 pos 与区间内能到达的最远位置 dis, 到达边界时跳跃次数加一;

const jump = (nums) => {
  let res = 0;
  let pos = 0; // 当前跳跃能覆盖的边界
  let dis = 0; // 边界内能到达的最远位置
  for (let i = 0; i < nums.length; i++) {
    if (pos >= nums.length - 1) break;
    dis = Math.max(dis, i + nums[i]);
    if (pos === i) {
      pos = dis; // 到达边界才真正跳一次
      res++;
    }
  }
  return res;
};

• 复杂度: 时间 $O(n)$, 空间 $O(1)$;
• 易错点: 计数必须在 pos === i 时执行, 否则会把同一跳内的扫描误计为多次跳跃;

移掉 k 位数字如何用单调栈贪心？

• 目标: 删除 $k$ 个数字, 使剩余数字按原顺序组成的数最小;
• 贪心选择性质: 高位数字越小越好, 所以遇到比栈顶更小的数字时弹出栈顶;
• 实现: 用单调递增栈遍历, 每弹出一个数字就消耗一次删除额度;
• 收尾: 遍历结束后若额度未用完, 从栈顶继续弹出; 结果需去掉前导 0;

const removeKdigits = (num, k) => {
  const stack = [];
  for (const ch of num) {
    while (k > 0 && stack.length !== 0 && ch < stack[stack.length - 1]) {
      stack.pop();
      k--;
    }
    if (ch !== "0" || stack.length !== 0) stack.push(ch); // 跳过前导 0
  }
  while (k > 0) {
    stack.pop();
    k--;
  }
  return stack.length === 0 ? "0" : stack.join("");
};

• 复杂度: 时间 $O(n)$, 空间 $O(n)$;
• 关联: 单调栈的完整讲解见同 collection 的「栈与单调栈」目录;

分发糖果如何用两次遍历贪心？

• 目标: 每个孩子至少 1 颗糖, 相邻且评分更高的孩子必须拿到更多糖;
• 贪心选择性质: 先满足左规则, 再满足右规则, 两次都取较大值即可同时满足两侧;
• 实现: 初始化全为 1; 正序遍历处理 ratings[i] > ratings[i-1]; 倒序遍历处理 ratings[i] > ratings[i+1];
• 倒序原因: 右规则依赖右侧孩子的结果, 必须从右往左算;

const candy = (ratings) => {
  const n = ratings.length;
  const res = new Array(n).fill(1);
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) res[i] = res[i - 1] + 1;
  }
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) res[i] = Math.max(res[i], res[i + 1] + 1);
  }
  return res.reduce((a, b) => a + b, 0);
};

• 复杂度: 时间 $O(n)$, 空间 $O(n)$;
• 关键: 第二遍必须取 Math.max, 否则会破坏第一遍已经满足的左规则;

加油站如何贪心找出唯一可行起点？

• 目标: 找出能绕环路行驶一周的出发加油站;
• 前置判定: 总油量 sum(gas) - sum(cost) 小于 0 时一定无解;
• 贪心选择性质: 若从 start 出发到 i 时累计油量转负, 则 [start, i] 内任何起点都不可行, 直接从 i + 1 重试;
• 依据: 把每站净收益看作 [+, -, ..., +, +], 总和为正时必然存在多个正收益子段的组合;

const canCompleteCircuit = (gas, cost) => {
  let total = 0; // 全程净油量
  let tank = 0; // 当前起点出发的剩余油量
  let start = 0;
  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    total += diff;
    tank += diff;
    if (tank < 0) {
      start = i + 1; // 该区间内任何起点都不可行
      tank = 0;
    }
  }
  return total < 0 ? -1 : start;
};

• 复杂度: 时间 $O(n)$, 空间 $O(1)$;
• 结论: 题目保证解唯一, 所以第一个满足条件的 start 即为答案;