1705. 吃苹果的最大数目 : 经典优先队列（堆）贪心运用题

题目描述

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

Tag : 「贪心」、「优先队列」、「堆」

有一棵特殊的苹果树，一连 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 == napples.length==n
• days.length == ndays.length==n
• 1 <= n <= 2 * 10^41<=n<=2∗104
• 0 <= apples[i], days[i] <= 2 * 10^40<=apples[i],days[i]<=2∗104
• 只有在 apples[i] = 0 时，days[i] = 0 才成立

贪心 + 优先队列（堆）

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

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

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

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

• 首先，如果「time < ntime<n」或者「堆不为空」，说明「还有苹果未被生成」或者「未必吃掉」，继续模拟；
  
• 在当日模拟中，如果「time < ntime<n」，说明当天有苹果生成，先将苹果 以二元组 (time + days[time] - 1, apples[time])(time+days[time]−1,apples[time]) 形式加入小根堆中；

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

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

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

假设使用上述吃法得到的苹果序列为 (a_1, a_2, ... ,a_n)(a1,a2,...,an)，而真实最优解对应序列为 (b_1, b_2, ..., b_m)(b1,b2,...,bm)。

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

起始，我们先证明边界成立，即 b_1b1 可以为 a_1a1。

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

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

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

• a_1a1 不存在与 (b_2, b_3, ..., b_m)(b2,b3,...,bm) 当中，此时直接用 a_1a1 替换 b_1b1 自然不会对后面的序列产生影响，也就是说替换后，最优序列合法性仍有保证，同时长度不变，结果不会变差；
  
• a_1a1 为 (b_2, b_3, ..., b_m)(b2,b3,...,bm) 中的某个，假设为 b_i = a_1bi=a1，由于 b_i/a_1bi/a1 在贪心解中的先出堆（过期时间最早），因此必然也有 b_i/a_1bi/a1 过期时间早于等于 b_1b1 的过期时间，此时将 b_1b1 放到 b_ibi 的位置仍是合法（过期时间比 b_i/a_1bi/a1 要晚），即将 b_1b1 和 b_i/a_1bi/a1 交换位置，最优序列合法性仍有保证，同时长度不变，结果不会变差。
  

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

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

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

代码：

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;
    }
}
复制代码

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

最后

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

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

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

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