What is the optimal approach for the 'Maximum Number of Eaten Apples' problem?

The optimal approach involves using a greedy strategy combined with a priority queue to prioritize eating apples that will rot soonest.

How does the priority queue help in solving this problem?

A priority queue helps efficiently track the apples available to eat, allowing for quick selection of apples that will rot the soonest.

Can the 'Maximum Number of Eaten Apples' problem be solved with dynamic programming?

While dynamic programming is a potential option, the greedy strategy combined with a priority queue is more efficient for this specific problem.

What is the time complexity of the solution to the 'Maximum Number of Eaten Apples' problem?

The time complexity is O(n log n) due to the heap operations required for inserting and removing apples.

How does the solution handle cases where no apples grow on a particular day?

The solution accounts for days with no apples by simply skipping those days and continuing the process with the next available apples.

#1705

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

吃苹果的最大数目

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

数组贪心堆（优先队列）

题目描述

有一棵特殊的苹果树，一连 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 才成立

lightbulb

解题思路

方法一：贪心 + 优先队列

我们可以贪心地在未腐烂的苹果中优先选择最容易腐烂的苹果，这样可以使得吃到的苹果尽可能多。

因此，我们可以用优先队列（小根堆）存储苹果的腐烂时间以及对应苹果的数量，每次从优先队列中取出腐烂时间最小的苹果，然后将其数量减一，若减一后苹果的数量不为零，则将其重新放入优先队列中。若苹果已经腐烂，则从优先队列中弹出。

时间复杂度 $O(n \times \log n + M)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{days}$ 的长度，而 $M = \max(\textit{days})$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution that handles the priority of rotting apples first.
question_mark
Candidates should demonstrate the ability to use a priority queue or heap for tracking the apples.
question_mark
Be cautious of inefficiencies when trying to handle the apples and days arrays.

warning

常见陷阱

外企场景

error
Not efficiently removing apples that have already rotted from the heap.
error
Failing to handle cases where no apples grow on a given day.
error
Not considering the scenario where you continue eating after the last day of apples.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the apples array has large gaps between days of growth?
arrow_right_alt
How would this solution change if you had a maximum number of apples you could eat per day?
arrow_right_alt
What if apples can be eaten multiple times before they rot?

help

常见问题

外企场景

继续练习

#1686 石子游戏 VI #1675 数组的最小偏移量 #1648 销售价值减少的颜色球