[Leetcode][1705. 吃苹果的最大数目] 贪心 + 优先队列:每天找最邻近过期的苹果吃

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 才成立

下面记录下我做这道题的思考过程:

暴力

很明显,每过一天,可能就有苹果过期,那么最好的方法是每天挑选最临近过期的苹果吃,这样才能吃到最多的苹果,于是新建一个二维数组,分别存储苹果个数和过期时间。

之后遍历这个数组,使用一个指针指向数组下标,一个timetime变量表示时间,时间每日递增,当苹果数>0> 0和未过期时苹果数1-1,如果不满足,数组下标idx++idx++,代码如下所示:

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;
}

但是,这个方法只通过了50个test cases,遇到下列用例就不适用了:

1
2
[2,1,1,4,5]
[10,10,6,4,2]

那么问题出在什么地方呢?

因为排序结果会导致我们先吃了还没有长出来的果实,所以此方法不可行,需要修改。

贪心 + 优先队列(堆)

思路与算法:

很明显,我们需要一种数据结构来记录过期时间最早的苹果,而且因为时间变化,所以需要可以删减元素,那么方法一的数组就不太可行,那么容易想到使用优先队列来存储苹果的过期时间,优先队列中最小的元素(即最早的腐烂日期)会最先被取出。

计算吃苹果的最大数目分成22个阶段:

  1. 第一阶段是第00天到第n1n-1天;
  2. 第二阶段是第nn天及以后。

首先,如果time<ntime<n或者堆不为空,如果当天有苹果生成(apple[time]>0)(apple[time]>0),先将苹果以二元组(apples[time],time+days[time])(apples[time], time + days[time])形式加入小根堆中,继续模拟;

然后尝试从堆中取出 最后食用日期最早可食用的苹果curcur,如果堆顶元素已过期,则抛弃;

如果吃掉curcur一个苹果后,仍有剩余,并且最后过期时间大于当前时间(尚未过期),将curcur重新入堆;

循环上述逻辑,直到所有苹果出堆。

代码如下所示:

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;
}

复杂度分析

  • 时间复杂度:O(nlogn)O(nlogn),其中nn是数组apples\textit{apples}days\textit{days}的长度。优先队列中最多有nn个元素,每个元素加入优先队列和从优先队列中取出各一次,每次操作的时间复杂度是O(logn)O(logn),因此总时间复杂度是O(nlogn)O(n \log n)

  • 空间复杂度:O(n)O(n),空间复杂度主要取决于优先队列,优先队列中的元素个数不会超过nn


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. 😉😃💗