题目描述

1705. 吃苹果的最大数目

题解

第一直觉是贪心，主要是找出贪心策略 。 因苹果过期后会腐烂，所以优先吃掉最近要过期的苹果会是最优解。

通过优先队列来维护苹果过期最小堆。

令 n为数组长度，time 为当前时间 ， res 为吃到的苹果数量

  1. 如果 time < n 且 堆不为空 说明还有苹果未生成 或者 未吃掉

  2. 当 time < n 则将苹果的过期日期及数量加入最小堆中

  3. 先剔除已过期的苹果，在取出堆顶的苹果，若还有剩余则重新 入队

  4. 重复以上逻辑知道所有的苹果出队

代码参考：

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
class Solution {
        public int eatenApples(int[] apples, int[] days) {
            //1.贪心策略，每次吃掉快过期的苹果 (重点,直觉上来看是贪心，但是要把握贪心的策略)
            // 贪心 + 优先队列
            PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
            //1.数组第一位为过期时间，2.第二位为剩余苹果数
            int time = 0;
            int res = 0;
            int n = apples.length;
            while (time < n || !queue.isEmpty()) {
                if (time < n && apples[time] > 0) {
                    int[] newApple = new int[]{time + days[time] - 1, apples[time]};
                    queue.add(newApple);
                }
                //剔除腐烂的苹果
                while (!queue.isEmpty() && queue.peek()[0] < time) {
                    queue.poll();
                }
                //获取快腐烂的苹果
                if (!queue.isEmpty()) {
                    int[] apple = queue.poll();
                    if (apple[1] > 0) {
                        //吃苹果
                        apple[1]--;
                        res++;
                    }
                    //重新入队
                    if (apple[1] > 0) {
                        queue.add(apple);
                    }
                }
                time++;
            }
            return res;
        }
    }