前提:
该题在 B 站上有 y 总的讲解:传送门
该题的讲解从 05:00 开始,建议先看视频讲解
思路:
该题是一道贪心题,同时应用了堆结构
贪心思路为:对于某一天,我们应该优先吃临近过期的苹果
视频里 y 总提到,和 145. 超市 一样
但其实仔细比较下来,还是有所不同:
对于 145. 超市 而言:
我们可以使用堆先预处理所有的商品,对于某一天而言,只需要找到最近的临近过期的商品即可
但该题还多了一个限制:当某一天吃苹果的时候,必须保证该苹果在改天已经被生产
这意味着我们不能先预处理出所有临近过期的苹果。因为预处理所有过期的商品,再决定哪一天吃哪个的话,会在某一天看到“尚未产生”的苹果,这是不合法的
举例说明:
假设我们在第 i 天生产了一个在 i + 20000 天过期的苹果(该苹果很久才过期),当我们来到第 i + 1 天的时候,我们会从堆中获取第 i + 2 天生产的当天过期的苹果(该苹果最邻近过期,但又来自于未来生产),这是不合法的操作。
为了避免这种不合法,我们在 1 ~ n 天,将当天的苹果加入堆之后,就决定该天要吃掉哪个苹果(这样堆中的所有的苹果都是之前生产的)
同时由于我们在度过 n 天后,可能还会有苹果剩余,所以我们还需要对堆中剩余的苹果再做一次处理
相应的代码如下:
class Solution {
public int eatenApples(int[] apples, int[] days) {
int n = apples.length;
PriorityQueue<int[]> d = new PriorityQueue<>((a, b) -> {
return a[0] - b[0];
});;
int ans = 0;
for (int i = 1; i <= n; i++) {
int apple = apples[i - 1];
int day = days[i - 1];
if (apple != 0) {
int last = i + day - 1;
d.add(new int[]{last, apple});
}
// 在 1 ~ n 天内,吃最早过期的苹果
while (!d.isEmpty() && d.peek()[0] < i) d.poll();
if (!d.isEmpty()) {
int[] cur = d.poll();
ans++;
if (--cur[1] > 0) d.add(cur);
}
}
// 到了第 n + 1 天,有苹果的话,继续吃
int idx = n + 1;
while (!d.isEmpty()) {
while (!d.isEmpty() && d.peek()[0] < idx) d.poll();
if (!d.isEmpty()) {
int[] cur = d.poll();
ans++;
if (--cur[1] > 0) d.add(cur);
}
idx++;
}
return ans;
}
}
观察上述代码发现,我们对 第1~n天 和 第n天之后 做了区分。
但是其实这里可以应用一个「边界」技巧:结合题意,n 最多为 20000,而一个苹果的有效期也最多是 20000。
所以我们不可能有一个苹果的有效期超过第 40000 天
这也是 y 总的代码所使用的技巧,非常实用。上述代码可以等效修改为:
class Solution {
public int eatenApples(int[] apples, int[] days) {
int n = apples.length;
PriorityQueue<int[]> d = new PriorityQueue<>((a, b)->{
return a[0] - b[0];
});
int ans = 0;
for (int i = 1; i <= 40001; i++) {
// 在 1 ~ n 天内,我们可以生产苹果,将苹果加入堆中
if (i <= n && apples[i - 1] > 0) {
int apple = apples[i - 1];
int day = days[i - 1];
int last = i + day - 1;
d.add(new int[]{last, apple});
}
while (!d.isEmpty() && d.peek()[0] < i) d.poll();
if (!d.isEmpty()) {
int[] cur = d.poll();
ans++;
if (--cur[1] > 0) d.add(cur);
}
}
return ans;
}
}