吃苹果的最大数目

吃苹果的最大数目(medium)

做题过程

一开始想的是用堆，但是问题是维护起来总感觉比较麻烦，就觉得可以用dp，但实际上dp无法解决这类前后耦合度较高的问题。

算法概述

原题

本题要求为给出下标天数长出的苹果数和它们的保质期，每天最多能吃一个苹果，计算最多能吃多少个。需要使用 贪心 每次从 优先队列 中找到保质期最短的先吃、

• 时间复杂度为O(nlogn)：排序，遍历剩余苹果渐进收敛于排序
• 空间复杂度为O(n)

JAVA

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        int ans = 0;
        // 最小堆
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
        int n = apples.length;
        int i = 0;
        // 遍历所有产出的天数
        while (i < n) {
            // 当堆顶代表的那天的的保质期已经超了，就弹出堆顶
            while (!pq.isEmpty() && pq.peek()[0] <= i) {
                pq.poll();
            }
            // 将days[i]转化为准确的时间
            int rottenDay = i + days[i];
            int count = apples[i];
            // 判断一下有没有产出苹果再加入堆中
            if (count > 0) {
                pq.offer(new int[]{rottenDay, count});
            }
            if (!pq.isEmpty()) {
                int[] arr = pq.peek();
                // 每天吃一个堆顶那天的产出的苹果
                arr[1]--;
                // 没苹果吃了也要弹出堆顶
                if (arr[1] == 0) {
                    pq.poll();
                }
                ans++;
            }
            i++;
        }
        // 遍历剩余苹果
        while (!pq.isEmpty()) {
            while (!pq.isEmpty() && pq.peek()[0] <= i) {
                pq.poll();
            }
            if (pq.isEmpty()) {
                break;
            }
            int[] arr = pq.poll();
            // 还剩多久保质期，能全吃就全吃了
            int curr = Math.min(arr[0] - i, arr[1]);
            // 批处理，不用一天天的遍历
            ans += curr;
            i += curr;
        }
        return ans;
    }
}

总结

题目被分为了两部分：

• 遍历所有产出天数，此时以天数为遍历单位
• 遍历剩余苹果（苹果才是问题核心，而不是天数），这里也是dp无法处理的部分，此时以剩下多少不同天数产出的苹果种类为遍历单位

我做的时候没有理清楚分成两部分的逻辑，想要把所有操作集成在一次循环内，所以会感觉格外复杂，本质上还是缺乏分层的思想。