LC 1705. 吃苹果的最大数目

题目描述

这是 LeetCode 上的 1705. 吃苹果的最大数目 ，难度为 中等。

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。

在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。

也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

示例 1：

输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]

输出：7

解释：你可以吃掉 7 个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。

示例 2：

输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]

输出：5

解释：你可以吃掉 5 个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的都是第六天长出来的苹果。

提示：

• $apples.length == n$
• $days.length == n$
• $1 <= n <= 2 * 10^4$
• $0 <= apples[i], days[i] <= 2 * 10^4$
• 只有在 apples[i] = 0 时，days[i] = 0 才成立

---

贪心 + 优先队列（堆）

这题是一道经典的结合优先队列（堆）的贪心题，与结合排序的贪心题一样，属于最为常见的贪心题型。

直觉上，我们会觉得「优先吃掉最快过期的苹果」会是最优，而这个维护苹果过期的过程，可以使用「小根堆」来实现。

苹果数量很大，但产生苹果的天数最多为 $2 * 10^4$，因此我们以二元组 (最后食用日期, 当日产生苹果数量) 的形式存入「小根堆」进行维护。

具体的，我们可以按照如下逻辑进行模拟（令 $n$ 为数组长度，$time$ 为当前时间，$ans$ 为吃到的苹果数量）：

• 首先，如果「$time < n$」或者「堆不为空」，说明「还有苹果未被生成」或者「未必吃掉」，继续模拟；

• 在当日模拟中，如果「$time < n$」，说明当天有苹果生成，先将苹果 以二元组 $(time + days[time] - 1, apples[time])$ 形式加入小根堆中；

  其中二元组表示 $(最后食用日期, 当日产生苹果数量)$，同时需要过滤 $apples[time] = 0$ 的情况。

• 然后尝试从堆中取出「最后食用日期」最早「可食用」的苹果 cur，如果堆顶元素已过期，则抛弃；
• 如果吃掉 cur 一个苹果后，仍有剩余，并且最后时间大于当前时间（尚未过期），将 cur 重新入堆；
• 循环上述逻辑，直到所有苹果出堆。

直观感受往往会骗人，我们使用「归纳法 + 反证法」证明上述猜想的正确性

假设使用上述吃法得到的苹果序列为 $(a_1, a_2, … ,a_n)$，而真实最优解对应序列为 $(b_1, b_2, …, b_m)$。

我们目的是证明 $n = m$，即吃掉苹果数量一致（贪心解是最优解的具体方案之一）。

起始，我们先证明边界成立，即 $b_1$ 可以为 $a_1$。

首先该替换操作必然不会使最优序列变长，否则就违背了最优解是长度最长的合法序列这一前提。

由于贪心解中每次总是取「过期时间最早的」苹果来吃，因此有 $a_1$ 过期时间小于等于 $b_1$ 过期时间，需要证明如果将最优解中的 $b_1$ 替换为 $a_1$，并不会影响整个序列的长度。

重点在与该操作是否会使得最优序列长度变短，这需要分情况讨论：

• $a_1$ 不存在与 $(b_2, b_3, …, b_m)$ 当中，此时直接用 $a_1$ 替换 $b_1$ 自然不会对后面的序列产生影响，也就是说替换后，最优序列合法性仍有保证，同时长度不变，结果不会变差；

• $a_1$ 为 $(b_2, b_3, …, b_m)$ 中的某个，假设为 $b_i = a_1$，由于 $b_i/a_1$ 在贪心解中的先出堆（过期时间最早），因此必然也有 $b_i/a_1$ 过期时间早于等于 $b_1$ 的过期时间，此时将 $b_1$ 放到 $b_i$ 的位置仍是合法（过期时间比 $b_i/a_1$ 要晚），即将 $b_1$ 和 $b_i/a_1$ 交换位置，最优序列合法性仍有保证，同时长度不变，结果不会变差。

当贪心解和最优解的首个位置决策相同（吃掉的苹果一样），下一位置决策所面临的条件完全相同，归纳推理所依赖的结构没有发生改变，上述分析同样成立。

也就是说，上述推理可以推广到最优解序列中的任意位置。

至此，我们证明出了最优解可以调整为我们的贪心序列，同时长度不变，即贪心解为最优解的具体方案之一。

代码：

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]);
        int n = apples.length, time = 0, ans = 0;
        while (time < n || !q.isEmpty()) {
            if (time < n && apples[time] > 0) q.add(new int[]{time + days[time] - 1, apples[time]});
            while (!q.isEmpty() && q.peek()[0] < time) q.poll();
            if (!q.isEmpty()) {
                int[] cur = q.poll();
                if (--cur[1] > 0 && cur[0] > time) q.add(cur);
                ans++;
            }
            time++;
        }
        return ans;
    }
}

• 时间复杂度：令 $n$ 为数组长度，最多有 $n$ 组苹果入堆/出堆。复杂度为 $O(n\log{n})$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1705 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。