【Leetcode 每日一题】1705. 吃苹果的最大数目

问题背景

有一棵特殊的苹果树，一连 $n$ 天，每天都可以长出若干个苹果。在第 $i$ 天，树上会长出 $apples[i]$ 个苹果，这些苹果将会在 $days[i]$ 天后（也就是说，第 $i+days[i]$ 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 $apples[i]=0$ 且 $days[i]=0$ 表示。
你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 $n$ 天之后继续吃苹果。
给你两个长度为 $n$ 的整数数组 $days$ 和 $apples$，返回你可以吃掉的苹果的最大数目。

数据约束

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

解题过程

一个比较明显的结论是，先吃接下来会最早腐烂的苹果会尽可能地减少损耗，进而最大化可能的时间。
最早腐烂可以用最小堆来维护，同时将相应的苹果数量也放进堆中，就可以方便地记录待处理的苹果相关信息了。

具体实现

class Solution {public int eatenApples(int[] apples, int[] days) {// 堆中的数对，维护苹果腐烂的时间和相应的数量Queue<int[]> heap = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);int res = 0;// 注意遍历完数组之后，如果仍有剩余的苹果，要继续计算时长for(int i = 0; i < apples.length || !heap.isEmpty(); i++) {// 腐烂的苹果出堆while(!heap.isEmpty() && heap.peek()[0] == i) {heap.poll();}// 维护堆中的苹果信息if(i < apples.length && apples[i] > 0) {heap.offer(new int[]{i + days[i], apples[i]});}if(!heap.isEmpty()) {res++;if(--heap.peek()[1] == 0) {heap.poll();}}}return res;}
}