[LeetCode] 每日一题 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 才成立

题解

解题思路

这是一个典型的贪心问题。为了最大化每天能吃的苹果数量，我们需要优先选择那些即将腐烂的苹果。同时，我们需要维护一个数据结构，用来动态管理每天生长的苹果及其对应的腐烂时间。

核心思路：

1. 优先队列（堆）：用优先队列存储苹果的腐烂时间和其来源天数，以便优先取出最早腐烂的苹果。

2. 动态更新：

• 每天增加新长出的苹果到队列中

• 移除已经腐烂的苹果

• 如果还有可食用的苹果，则吃掉一个

代码实现

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        // 优先队列，按照腐烂日期排序
        PriorityQueue<Integer> queue = new PriorityQueue<>((e1, e2) -> Integer.compare(e1 + days[e1], e2 + days[e2]));
        int ans = 0, n = apples.length, day = 0;
        
        // 遍历所有天数并处理队列
        while (!queue.isEmpty() || day < n) {
            // 添加当天长出的苹果
            if (day < n && apples[day] > 0) {
                queue.offer(day);
            }
            
            // 移除已经腐烂的苹果
            while (!queue.isEmpty() && queue.peek() + days[queue.peek()] <= day) {
                queue.poll();
            }
            
            // 吃一个苹果
            if (!queue.isEmpty()) {
                int temp = queue.poll();
                apples[temp]--;
                ans++;
                // 如果苹果未吃完，重新加入队列
                if (apples[temp] > 0) {
                    queue.offer(temp);
                }
            }
            
            day++;
        }
        
        return ans;
    }
}

复杂度分析

1. 时间复杂度：

• 每天我们需要进行一次队列操作（加入或移除元素），复杂度为 O(logk)，其中 k 为当前队列的大小。

• 在最坏情况下，队列的大小不会超过 n，因此总复杂度为 O(nlogn)。

2. 空间复杂度：

• 队列存储了所有未腐烂的苹果的来源天数，空间复杂度为 O(n)。

总结

通过维护一个优先队列，我们能够动态地选择即将腐烂的苹果，并尽可能多地吃掉它们，从而实现贪心策略的最优解。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。