问题背景
有一棵特殊的苹果树，一连
n
n
n 天，每天都可以长出若干个苹果。在第
i
i
i 天，树上会长出
a
p
p
l
e
s
[
i
]
apples[i]
apples[i] 个苹果，这些苹果将会在
d
a
y
s
[
i
]
days[i]
days[i] 天后（也就是说，第
i
+
d
a
y
s
[
i
]
i + days[i]
i+days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用
a
p
p
l
e
s
[
i
]
=
0
apples[i] = 0
apples[i]=0 且
d
a
y
s
[
i
]
=
0
days[i] = 0
days[i]=0 表示。
你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这
n
n
n 天之后继续吃苹果。
给你两个长度为
n
n
n 的整数数组
d
a
y
s
days
days 和
a
p
p
l
e
s
apples
apples，返回你可以吃掉的苹果的最大数目。
数据约束
- a p p l e s . l e n g t h = n apples.length = n apples.length=n
- d a y s . l e n g t h = n days.length = n days.length=n
- 1 ≤ n ≤ 2 × 1 0 4 1 \le n \le 2 \times 10 ^ 4 1≤n≤2×104
- 0 ≤ a p p l e s [ i ] , d a y s [ i ] ≤ 2 × 1 0 4 0 \le apples[i], days[i] \le 2 \times 10 ^ 4 0≤apples[i],days[i]≤2×104
- 只有在 a p p l e s [ i ] = 0 apples[i] = 0 apples[i]=0 时， d a y s [ i ] = 0 days[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;
}
}