Leetcode1705：吃苹果的最大数目

题目描述：

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

代码思路：

1. 初始化变量：
   • res：用于记录总共吃掉的苹果数量。
   • pq：一个最小堆（优先队列），用于存储苹果的腐烂日期和当前数量。堆中每个元素是一个列表，其中第一个元素是腐烂日期，第二个元素是当前剩余苹果数量。
   • day：当前的天数，从0开始。
2. 主循环：
   • 循环条件是 pq 非空或 day 小于 apples 列表的长度。这意味着只要还有苹果在堆中或者还有新的苹果会长出来，就继续循环。
3. 处理新长出的苹果：
   • 如果 day 小于 apples 列表的长度，说明今天有新苹果长出。将新苹果的腐烂日期（day + days[day]）和数量（apples[day]）作为一个列表推入堆 pq 中。
4. 移除腐烂和吃完的苹果：
   • 遍历堆 pq，移除所有已经腐烂（pq[0][0] <= day）或已经被吃完（pq[0][1] == 0）的苹果。这一步保证了堆中只包含还可以吃的苹果。
5. 吃苹果：
   • 如果堆 pq 不为空，说明还有可以吃的苹果。将 res 增加1（表示吃掉一个苹果），并将堆顶元素（最早腐烂的苹果）的数量减1。
6. 天数递增：
   • 将 day 增加1，表示进入下一天。
7. 返回结果：
   • 当循环结束时，返回 res，即总共吃掉的苹果数量。

关键点：

• 使用最小堆（优先队列）来管理苹果的腐烂日期，确保总是优先吃最早会腐烂的苹果。
• 堆中存储的是苹果的腐烂日期和剩余数量，通过更新数量来模拟吃苹果的过程。
• 循环条件确保所有可能长出的苹果都被考虑，并且只要堆中还有苹果或者还有新的苹果会长出，就继续循环。

代码实现：

from typing import List
from heapq import heappop, heappush

# 在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂
# 你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。
class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        res = 0
        pq = []
        day = 0
        while pq or day < len(apples):
            if day < len(apples):
                heappush(pq, [day + days[day], apples[day]])
            while pq and (pq[0][0] <= day or pq[0][1] == 0):
                heappop(pq)
            if pq:
                res += 1
                pq[0][1] -= 1
            day += 1
        return res