题目描述

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后腐烂，变得无法食用。你打算每天最多吃一个苹果，以保持营养均衡。返回你可以吃掉的苹果的最大数目。

例如：apples = [1,2,3,5,2]，days = [3,2,1,4,2]，输出 7。

解题思路

核心贪心策略

这是一个经典的贪心 + 最小堆问题。为了最大化吃掉的苹果数量，每天应该优先吃掉最早腐烂的苹果（即过期时间最早的苹果）。这样可以避免苹果在腐烂前没有被吃掉。

数据结构

定义一个 Apple 类，包含两个属性：

  • count：该批次苹果的剩余数量。
  • days：该批次苹果的过期时间（即 i + days[i]），在 days 天之前（不含当天）可以食用。

使用最小堆按过期时间 days 排序，堆顶始终是即将最早腐烂的苹果。

算法步骤

  1. 初始化最小堆 heap，计数器 res = 0，天数 i = 0。
  2. 当 i < n（还有苹果在生长）或堆非空（还有苹果可以吃）时进行循环：
    • 添加当天的苹果：如果 i < n 且 apples[i] > 0，将 (apples[i], i + days[i]) 插入堆中。
    • 清理过期苹果：不断弹出堆顶，如果堆顶苹果的过期时间 <= i（即已经过期），将其丢弃；否则放回堆中并停止清理。
    • 吃苹果：如果堆非空，弹出堆顶（最早过期的苹果）：
      • res++（吃掉一个）。
      • 该批次剩余数量减 1，如果还有剩余，重新插入堆中。
    • i++，进入下一天。
  3. 返回 res。

示例说明

以 apples = [1,2,3,5,2]，days = [3,2,1,4,2] 为例（部分模拟）：

  • 第 0 天：添加苹果 (1个，第3天过期)。清理：无过期。吃：吃1个。res=1。
  • 第 1 天：添加苹果 (2个，第3天过期)。清理：无过期。吃：吃最早过期的（第3天那批）。res=2。
  • …依此类推。

为什么贪心是正确的？

如果我们不优先吃最早腐烂的苹果，那么一些即将腐烂的苹果就会浪费掉。贪心选择总是消耗”最紧迫”的苹果，保证不浪费任何可以在腐烂前被吃掉的苹果。

复杂度分析

  • 时间复杂度：O((n + res) * log n)，每天最多进行一次插入和删除操作，堆的大小不超过 n。
  • 空间复杂度：O(n)，堆中最多存储 n 个批次的苹果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package code.J1705;

import datastructure.MyMinHeap;

class Apple implements Comparable<Apple> {
    private int count;
    private int days;
    public Apple(int count, int days) { this.count = count; this.days = days; }
    public int getCount() { return count; }
    public void setCount(int count) { this.count = count; }
    public int getDays() { return days; }
    public void setDays(int days) { this.days = days; }
    @Override
    public int compareTo(Apple o) { return this.days - o.getDays(); }
}

public class J1705 {
    public int eatenApples(int[] apples, int[] days) {
        MyMinHeap<Apple> heap = new MyMinHeap<>(apples.length);
        int res = 0;
        int i = 0;
        int n = apples.length;
        while (i < n || !heap.isEmpty()) {
            if (i < n && apples[i] > 0) {
                heap.insert(new Apple(apples[i], i + days[i]));
            }
            while (!heap.isEmpty()) {
                Apple top = heap.extractMin();
                if (top.getDays() > i) { heap.insert(top); break; }
            }
            if (!heap.isEmpty()) {
                Apple earliest = heap.extractMin();
                res++;
                earliest.setCount(earliest.getCount() - 1);
                if (earliest.getCount() > 0) heap.insert(earliest);
            }
            i++;
        }
        return res;
    }
}