Medium

题目描述

有一棵特殊的苹果树，一连 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 个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的是第六天长出来的苹果。

提示：

  • n == apples.length == days.length
  • 1 <= n <= 2 * 10^4
  • 0 <= apples[i], days[i] <= 2 * 10^4
  • 只有在 apples[i] = 0 时，days[i] = 0 才成立，反之亦然。

解题思路

这是一道贪心算法题，核心思路是优先吃掉即将腐烂的苹果。

解题思路：

  1. 优先队列存储苹果信息：使用最小堆来存储苹果的腐烂日期，确保我们总是先吃掉最早腐烂的苹果。每个元素存储 (腐烂日期, 剩余苹果数量)。

  2. 贪心策略：每天只吃一个苹果，优先选择最早腐烂的苹果吃掉。这样可以最大化吃到的苹果总数。

  3. 模拟过程：

    • 从第0天开始模拟
    • 每天先将新长出的苹果（如果有）加入优先队列
    • 清理已经腐烂的苹果
    • 如果有可吃的苹果，选择最早腐烂的那批吃一个
    • 继续下一天，直到没有可吃的苹果

  4. 边界处理：即使过了前n天，只要还有没腐烂的苹果，就可以继续吃。

时间复杂度分析：由于我们最多处理2万天，每天的堆操作为O(log n)，所以总体时间复杂度较为合理。

代码实现

class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        int eaten = 0;
        int day = 0;
        
        while (day < apples.size() || !pq.empty()) {
            // 添加当天长出的苹果
            if (day < apples.size() && apples[day] > 0) {
                pq.push({day + days[day], apples[day]});
            }
            
            // 移除已经腐烂的苹果
            while (!pq.empty() && pq.top().first <= day) {
                pq.pop();
            }
            
            // 吃掉一个苹果
            if (!pq.empty()) {
                auto [rotDay, count] = pq.top();
                pq.pop();
                eaten++;
                if (count > 1) {
                    pq.push({rotDay, count - 1});
                }
            }
            
            day++;
        }
        
        return eaten;
    }
};

class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        import heapq
        
        heap = []
        eaten = 0
        day = 0
        
        while day < len(apples) or heap:
            # 添加当天长出的苹果
            if day < len(apples) and apples[day] > 0:
                heapq.heappush(heap, (day + days[day], apples[day]))
            
            # 移除已经腐烂的苹果
            while heap and heap[0][0] <= day:
                heapq.heappop(heap)
            
            # 吃掉一个苹果
            if heap:
                rot_day, count = heapq.heappop(heap)
                eaten += 1
                if count > 1:
                    heapq.heappush(heap, (rot_day, count - 1))
            
            day += 1
        
        return eaten

public class Solution {
    public int EatenApples(int[] apples, int[] days) {
        var pq = new PriorityQueue<(int rotDay, int count), int>();
        int eaten = 0;
        int day = 0;
        
        while (day < apples.Length || pq.Count > 0) {
            // 添加当天长出的苹果
            if (day < apples.Length && apples[day] > 0) {
                pq.Enqueue((day + days[day], apples[day]), day + days[day]);
            }
            
            // 移除已经腐烂的苹果
            while (pq.Count > 0 && pq.Peek().rotDay <= day) {
                pq.Dequeue();
            }
            
            // 吃掉一个苹果
            if (pq.Count > 0) {
                var (rotDay, count) = pq.Dequeue();
                eaten++;
                if (count > 1) {
                    pq.Enqueue((rotDay, count - 1), rotDay);
                }
            }
            
            day++;
        }
        
        return eaten;
    }
}

var eatenApples = function(apples, days) {
    const heap = [];
    let eaten = 0;
    let day = 0;
    
    const push = (rotDay, count) => {
        heap.push([rotDay, count]);
        heap.sort((a, b) => a[0] - b[0]);
    };
    
    const pop = () => {
        return heap.shift();
    };
    
    while (day < apples.length || heap.length > 0) {
        // 添加当天长出的苹果
        if (day < apples.length && apples[day] > 0) {
            push(day + days[day], apples[day]);
        }
        
        // 移除已经腐烂的苹果
        while (heap.length > 0 && heap[0][0] <= day) {
            pop();
        }
        
        // 吃掉一个苹果
        if (heap.length > 0) {
            const [rotDay, count] = pop();
            eaten++;
            if (count > 1) {
                push(rotDay, count - 1);
            }
        }
        
        day++;
    }
    
    return eaten;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n log n)，其中 n 为数组长度。最坏情况下需要处理约 2n 天，每天的堆操作为 O(log n)
空间复杂度O(n)，优先队列最多存储 n 批苹果信息