1705. 吃苹果的最大数目

approach 1，优先队列+贪心

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        // int[]{target_day, apple_cnt}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        int n = apples.length;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            while (!pq.isEmpty() && (pq.peek()[0] <= i || pq.peek()[1] <= 0)) {
                pq.poll();
            }
            if (apples[i] != 0) {
                pq.offer(new int[]{i+days[i], apples[i]});
            }
            if (!pq.isEmpty()) {
                pq.peek()[1]--;
                cnt++;
            }
        }

        int curDay = n;
        while (!pq.isEmpty()) {
            while (!pq.isEmpty() && (pq.peek()[0] <= curDay || pq.peek()[1] <= 0)) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                pq.peek()[1]--;
                cnt++;
            }
            curDay++;
        }

        return cnt;
    }
}

优化，使用d（当前日期）放入到优先队列中，不需要构造新的数组

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> days[a] - days[b]);
        int cnt = 0;
        int d = 0;
        while (d < days.length) {
            while (!pq.isEmpty() && (apples[pq.peek()] == 0 || days[pq.peek()] <= d)) {
                pq.poll();
            }

            if (apples[d] != 0) {
                days[d] += d;
                pq.offer(d);
            }

            if (!pq.isEmpty()) {
                apples[pq.peek()]--;
                cnt++;
            }
            d++;
        }

        while (!pq.isEmpty()) {
            while (!pq.isEmpty() && (days[pq.peek()] <= d || apples[pq.peek()] == 0)) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                apples[pq.peek()]--;
                cnt++;
            }
            d++;
        }

        return cnt;
    }
}

更简洁的写法，将情况分类得更清晰了：

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int d = 0, n = days.length, cnt = 0;
        while (d < n || !pq.isEmpty()) {
            if (d < n && apples[d] > 0) pq.offer(new int[]{d + days[d], apples[d]});
            while (!pq.isEmpty() && pq.peek()[0] <= d) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                int[] p = pq.peek();
                if (--p[1] == 0) pq.poll();
                cnt++;
            }
            d++;
        }
        return cnt;
    }
}