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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 3 分钟

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

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

暴力

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

之后遍历这个数组，使用一个指针指向数组下标，一个 \(time\) 变量表示时间，时间每日递增，当苹果数 \(> 0\) 和未过期时苹果数 \(-1\)，如果不满足，数组下标\(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]

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

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

贪心 + 优先队列（堆）

思路与算法：

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

计算吃苹果的最大数目分成 \(2\) 个阶段：

  1. 第一阶段是第 \(0\) 天到第 \(n-1\) 天；
  2. 第二阶段是第 \(n\) 天及以后。

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

然后尝试从堆中取出 最后食用日期最早可食用的苹果 \(cur\)，如果堆顶元素已过期，则抛弃；

如果吃掉 \(cur\) 一个苹果后，仍有剩余，并且最后过期时间大于当前时间（尚未过期），将 \(cur\) 重新入堆；

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

代码如下所示：

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)\)，其中 \(n\) 是数组 \(\textit{apples}\) 和 \(\textit{days}\) 的长度。优先队列中最多有 \(n\) 个元素，每个元素加入优先队列和从优先队列中取出各一次，每次操作的时间复杂度是 \(O(logn)\)，因此总时间复杂度是 \(O(n \log n)\)。

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

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