LeetCode 1705：吃苹果的最大数目——最早过期优先

题目

第 i 天会长出 apples[i] 个苹果，这些苹果在第 i + days[i] 天腐烂。每天最多吃一个苹果，问最多能吃多少个。

如果第 i 天长出苹果，且 days[i] = 3，那么这些苹果可以在第 i、i + 1、i + 2 天食用，在第 i + 3 天开始失效。

贪心思路

每天最多只能吃一个苹果，因此应该优先吃最早腐烂的苹果：

把当天新长出的苹果加入堆中。
删除已经过期的苹果批次。
如果还有苹果，吃掉过期时间最早的那一批。
当原始天数结束后，继续处理堆中尚未过期的苹果。

为什么不能优先吃最新的苹果？因为更早过期的苹果一旦错过就无法再吃，而较晚过期的苹果还可以留到后面。因此“最早过期优先”可以避免当前选择造成不可逆的浪费。

用最小堆维护苹果批次

每个堆元素保存两个值：

expire：这批苹果失效的日期。
count：这批还剩多少个。

JavaScript 没有内置最小堆，先实现一个按 expire 升序排列的最小堆：

javascript 复制代码 <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="lucide lucide-circle-chevron-left md-editor-icon"><circle cx="12" cy="12" r="10"/><path d="m14 16-4-4 4-4"/></svg>

class MinHeap {
  constructor(compare) {
    this.data = [];
    this.compare = compare;
  }

  get size() {
    return this.data.length;
  }

  peek() {
    return this.data[0];
  }

  push(value) {
    this.data.push(value);
    this.#siftUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }

    const top = this.data[0];
    const last = this.data.pop();

    if (this.data.length > 0) {
      this.data[0] = last;
      this.#siftDown(0);
    }

    return top;
  }

  #siftUp(index) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);

      if (this.compare(this.data[parent], this.data[index]) <= 0) {
        break;
      }

      [this.data[parent], this.data[index]] = [
        this.data[index],
        this.data[parent],
      ];
      index = parent;
    }
  }

  #siftDown(index) {
    while (true) {
      const left = index * 2 + 1;
      const right = index * 2 + 2;
      let smallest = index;

      if (
        left < this.data.length &&
        this.compare(this.data[left], this.data[smallest]) < 0
      ) {
        smallest = left;
      }

      if (
        right < this.data.length &&
        this.compare(this.data[right], this.data[smallest]) < 0
      ) {
        smallest = right;
      }

      if (smallest === index) {
        break;
      }

      [this.data[index], this.data[smallest]] = [
        this.data[smallest],
        this.data[index],
      ];
      index = smallest;
    }
  }
}

完整代码

function eatenApples(apples, days) {
  const heap = new MinHeap((a, b) => a.expire - b.expire);
  let eaten = 0;
  let day = 0;

  while (day < apples.length || heap.size > 0) {
    if (day < apples.length && apples[day] > 0 && days[day] > 0) {
      heap.push({
        expire: day + days[day],
        count: apples[day],
      });
    }

    while (heap.size > 0 && heap.peek().expire <= day) {
      heap.pop();
    }

    if (heap.size > 0) {
      const batch = heap.peek();
      batch.count -= 1;
      eaten += 1;

      if (batch.count === 0) {
        heap.pop();
      }
    }

    day += 1;
  }

  return eaten;
}

console.log(eatenApples([1, 2, 3, 5, 2], [3, 2, 1, 4, 2])); // 7
console.log(eatenApples([3, 0, 0, 0, 0, 2], [3, 0, 0, 0, 0, 2])); // 5

复杂度分析

设 n 是给定天数，k 是实际加入堆中的苹果批次数：

每批苹果入堆一次，复杂度为 O(log k)。
每批苹果最多出堆一次，复杂度为 O(log k)。
总时间复杂度为 O((n + k) log k)，通常可以写成 O(n log n)。
堆的空间复杂度为 O(k)。

容易出错的地方

1. 过期日期不能写错

第 day 天生产、days[day] 天后腐烂的苹果，失效日期是 day + days[day]。循环中应在当天吃苹果前删除 expire <= day 的批次。

2. 苹果数量不需要展开

原文把一批苹果逐个放进数组，会造成不必要的内存和排序开销。使用 { expire, count } 保存批次即可。

3. 不要每天对整个数组排序

每天重新对所有苹果排序会产生较大开销，也不容易正确处理原始天数结束后的苹果。最小堆可以始终快速取得最早过期的批次。

4. 原始天数结束后仍然要继续吃

题目允许在 apples.length 天之后继续吃没有腐烂的苹果，所以循环条件必须包含 heap.size > 0。

总结

这道题的关键不是模拟每个苹果，而是维护“当前仍然有效、且最早过期”的苹果批次。用最小堆实现最早过期优先后，代码更短、更容易证明正确，也避免了原文中多份实验代码和超长随机测试数据带来的阅读干扰。