LeetCode刷题日记2021-12-241705. 吃苹果的最大数目-贪心&优先队列

LeetCode刷题日记2021-12-24/1705. 吃苹果的最大数目-贪心&优先队列

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 才成立

题解思路

贪心算法要求我们总想把当天生产苹果吃完才去判断下一天生长的苹果

因此我们用优先队列存储为苹果过期的天 以及 苹果的数量

我们用优先队列存储会保证我们吃的 永远是最旧日期生产 的苹果

• 当苹果未过期时 我们总是吃这天生产的苹果
• 当苹果过期之后，我们才吃下一天生产的苹果

我们将吃苹果分为 苹果生长天数之内 及 苹果生长天数之后 也就是 i在apples数组内 跟 apples数组外

• 当i在apples数组内，我们将【苹果过期的天 以及 苹果数量存储】

  • 直到苹果过期的当天 我们都一直吃该天的苹果

  • 当苹果过期或者数量为0时候 我们将其d出 并开始吃下一天的

• 当i在apples数组外的时候 我们将 到达过期天数的数量 与 苹果的数量 做对比取其最小值

题解代码

class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
    	ans,pq,i=0,[],0
		#当i在数组内
		while i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5690840.html