吃苹果的最大数目

难度: 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 个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的都是第六天长出来的苹果。

提示：

apples.length == n
days.length == n
1 <= n <= 2 * 10⁴
0 <= apples[i], days[i] <= 2 * 10⁴
只有在 apples[i] = 0 时，days[i] = 0 才成立

Submission

运行时间: 151 ms

内存: 20.4 MB

class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        h = []
        cnt = 0
        for k, c in enumerate(apples):
            while h and h[0][0] <= k:
                heappop(h)
            if c:
                heappush(h, [k + days[k], c])
            if h:
                cnt += 1
                if h[0][1] == 1:
                    heappop(h)
                else:
                    h[0][1] -= 1
        k += 1
        while h:
            a, b = heappop(h)
            t = min(a - k, b)
            k += t
            cnt += t    
        return cnt

Explain

题解采用了贪心算法和优先队列（最小堆）来解决问题。每天都会检查新长出的苹果并记录它们腐烂的日期和数量。使用最小堆是为了每天都能优先吃掉最先腐烂的苹果。堆中每个元素是一个列表，其中第一个元素是苹果腐烂的日期，第二个元素是苹果的数量。每天开始时，会移除所有已经腐烂的苹果。如果当天有新苹果，就将其添加到堆中。接着，如果堆不为空，表示还有未腐烂的苹果，就吃掉一个，并相应地更新堆。遍历完所有的天数后，还需要处理堆中剩余的苹果，直到所有的苹果都被吃完或腐烂。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        # 初始化最小堆
        h = []
        # 吃掉的苹果总数
        cnt = 0
        # 遍历每一天
        for k, c in enumerate(apples):
            # 清除所有已经腐烂的苹果
            while h and h[0][0] <= k:
                heappop(h)
            # 如果今天有新苹果，加入堆中
            if c:
                heappush(h, [k + days[k], c])
            # 如果堆不为空，吃掉一个最先腐烂的苹果
            if h:
                cnt += 1
                # 如果这是最后一个苹果，从堆中移除它
                if h[0][1] == 1:
                    heappop(h)
                else:
                    # 否则减少一个苹果数量
                    h[0][1] -= 1
        # 处理完所有的天数后，处理剩余的苹果
        k += 1
        while h:
            a, b = heappop(h)
            t = min(a - k, b)
            k += t
            cnt += t    
        return cnt

Explore

在处理剩余苹果的循环中，循环终止的条件是堆为空。堆中存储了所有尚未腐烂的苹果及其腐烂日期。在每次循环中，从堆中取出最先腐烂的苹果（堆顶元素），计算可以吃的苹果数量，这是通过取腐烂日期与当前日期之差和苹果数量的较小值来决定的。吃完这些苹果或者达到腐烂日期，当前日期更新为腐烂日期或增加与吃苹果数量相等的天数。这样确保了所有可以吃的苹果都被正确计算，直到没有更多的苹果可以吃（即堆为空）。

算法在每天的开始使用一个循环来检查并移除所有已经腐烂的苹果。堆（最小堆）的顶部存储的是最早腐烂的苹果。在循环中，检查堆顶苹果的腐烂日期是否小于或等于当前天数。如果是，使用 `heappop` 函数从堆中移除这些苹果。循环继续，直到堆顶的苹果腐烂日期大于当前日期，确保了所有在当天或之前腐烂的苹果都被及时移除。

在添加新苹果到堆中时，算法首先计算每批新苹果的腐烂日期（当前日期加上苹果的持续天数）。如果这个腐烂日期等于当前日期，这批苹果当天就会腐烂，因此，它们不会被添加到堆中，即避免了无用的操作。只有当腐烂日期大于当前日期时，这批苹果才被添加到堆中，这样确保了堆中只存储那些至少能存活到第二天的苹果。

算法使用的最小堆自然地处理了这一优先选择问题。在最小堆中，堆顶元素总是腐烂日期最早的苹果。每天只能吃一个苹果时，直接从堆顶取苹果吃掉。这确保了优先吃掉那些即将在当天或次日腐烂的苹果，从而最大化苹果的使用效率并减少浪费。