当前位置：首页 > article >正文

Leetcode打卡：吃苹果的最大数目

article 2024/12/25 5:42:12

执行结果：通过

题目：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 * 104
0 <= apples[i], days[i] <= 2 * 104
只有在 apples[i] = 0 时，days[i] = 0 才成立

代码以及解题思路

代码：

class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        n = len(days)
        i = ans = 0
        q = []
        while i < n or q:
            if i < n and apples[i]:
                heappush(q, (i + days[i] - 1, apples[i]))
            while q and q[0][0] < i:
                heappop(q)
            if q:
                t, v = heappop(q)
                v -= 1
                ans += 1
                if v and t > i:
                    heappush(q, (t, v))
            i += 1
        return ans

解题思路：

初始化变量：
- n：表示 days 列表的长度，也即天数。
- i：当前的天数，从0开始。
- ans：累计吃掉的苹果数量，初始化为0。
- q：一个优先队列（最小堆），用于存储苹果的新鲜期限和数量。堆中的元素是元组 (过期日期, 苹果数量)。
遍历每一天：
- 使用一个 while 循环，条件是 i < n 或 q 不为空。这是因为即使天数超过了 n，堆中可能还有未过期的苹果。
处理新获得的苹果：
- 如果 i < n 且 apples[i] 不为0（即第 i 天有苹果），则将这批苹果及其过期日期加入堆中。过期日期计算为 i + days[i] - 1。
移除过期苹果：
- 在堆不为空的情况下，如果堆顶的苹果已经过期（即堆顶元素的过期日期小于当前天数 i），则将其从堆中移除。
吃掉苹果：
- 如果堆不为空，从堆中取出最早过期的苹果（堆顶元素），将其数量减1，并将吃掉的苹果数量加到 ans 上。
- 如果这批苹果还有剩余（数量大于0）且未过期（过期日期大于当前天数），则将其重新加入堆中。
天数递增：
- 将天数 i 加1，继续处理下一天。
返回结果：
- 当所有天数都处理完毕且堆为空时，返回累计吃掉的苹果数量 ans。