By Long Luo
Leetcode 1705. 吃苹果的最大数目 题目如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| 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 才成立
|
下面记录下我做这道题的思考过程：
暴力
很明显，每过一天，可能就有苹果过期，那么最好的方法是每天挑选最临近过期的苹果吃，这样才能吃到最多的苹果，于是新建一个二维数组，分别存储苹果个数和过期时间。
之后遍历这个数组，使用一个指针指向数组下标，一个 变量表示时间，时间每日递增，当苹果数 和未过期时苹果数 ，如果不满足，数组下标，代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public int eatenApples(int[] apples, int[] days) {
int len = apples.length;
int ans = 0;
int[][] sorted = new int[len][2];
for (int i = 0; i < len; i++) {
sorted[i][0] = apples[i];
sorted[i][1] = i + days[i];
}
Arrays.sort(sorted, (o1, o2) -> o1[1] - o2[1]);
int time = 0;
int idx = 0;
while (idx < len) {
while (idx < len && (sorted[idx][0] <= 0 || sorted[idx][1] <= time)) {
idx++;
}
if (idx < len && sorted[idx][1] > time) {
sorted[idx][0]--;
ans++;
}
time++;
}
return ans;
}
|
但是，这个方法只通过了 个test cases，遇到下列用例就不适用了：
1
2
| [2,1,1,4,5]
[10,10,6,4,2]
|
那么问题出在什么地方呢？
因为排序结果会导致我们先吃了还没有长出来的果实，所以此方法不可行，需要修改。
贪心 + 优先队列（堆）
思路与算法：
很明显，我们需要一种数据结构来记录过期时间最早的苹果，而且因为时间变化，所以需要可以删减元素，那么方法一的数组就不太可行，那么容易想到使用优先队列来存储苹果的过期时间，优先队列中最小的元素（即最早的腐烂日期）会最先被取出。
计算吃苹果的最大数目分成 个阶段：
- 第一阶段是第 天到第 天；
- 第二阶段是第 天及以后。
首先，如果 或者堆不为空，如果当天有苹果生成 ，先将苹果以二元组 形式加入小根堆中，继续模拟；
然后尝试从堆中取出 最后食用日期最早可食用的苹果 ，如果堆顶元素已过期，则抛弃；
如果吃掉 一个苹果后，仍有剩余，并且最后过期时间大于当前时间（尚未过期），将 重新入堆；
循环上述逻辑，直到所有苹果出堆。
代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| public int eatenApples(int[] apples, int[] days) {
if (apples == null || apples.length == 0 || days == null || days.length == 0) {
return 0;
}
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int len = apples.length;
int ans = 0;
int time = 0;
while (time < len || !pq.isEmpty()) {
if (time < len && apples[time] > 0) {
pq.offer(new int[]{apples[time], days[time] + time});
}
while (!pq.isEmpty() && pq.peek()[1] <= time) {
pq.poll();
}
if (!pq.isEmpty()) {
int[] curr = pq.poll();
curr[0]--;
ans++;
if (curr[0] > 0 && curr[1] > time) {
pq.offer(curr);
}
}
time++;
}
return ans;
}
|
复杂度分析
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗
预览: