LeetCode吃苹果问题解析：优先队列的贪心算法应用

发布时间：2026/10/24 6:54:57
LeetCode吃苹果问题解析：优先队列的贪心算法应用

1. 项目概述：LeetCode吃苹果问题与队列应用

这道来自LeetCode的编程题编号为1705，题目描述如下：有一棵特殊的苹果树，一连n天每天都会长出若干个苹果。在第i天，树上会长出apples[i]个苹果，这些苹果会在days[i]天后腐烂（即第i天长的苹果在第i+days[i]天会腐烂）。你每天最多可以吃一个苹果，且可以选择不吃。假设你可以在任意天数吃苹果（不一定要连续），求最多可以吃多少个苹果。

这个问题看似简单，但实际考察了对优先队列（堆）这种数据结构的理解和灵活运用能力。我在第一次遇到这个问题时，花了整整两小时才找到最优解，期间踩过不少坑，今天就把我的解题思路和优化过程完整分享给大家。

2. 问题分析与数据结构选择

2.1 问题核心难点解析

这道题的关键在于每天都要做出最优选择：吃哪个苹果才能最大化总数量？直觉告诉我们应该优先吃最快腐烂的苹果，这就是典型的贪心算法思想。但如何高效实现这个策略呢？

举个例子：第1天长了5个苹果（保质期3天），第2天长了2个苹果（保质期1天）。如果第1天随便吃一个苹果，可能第2天就必须吃第1天的苹果（因为第2天的苹果会在第3天腐烂），这样最多吃2个。但如果第1天不吃，第2天吃第2天的苹果（因为保质期更短），第3天再吃第1天的苹果，这样就能吃3个。

2.2 队列数据结构对比

我们需要一个能随时获取最快腐烂苹果的数据结构，常见候选有：

  • 普通数组：每次需要O(n)时间查找，效率太低
  • 排序数组：插入时需要O(nlogn)排序，不理想
  • 优先队列（最小堆）：插入和取出都是O(logn)，完美匹配需求

优先队列的堆实现可以保证堆顶元素始终是最小值（即最早腐烂的苹果）。Python中可以使用heapq模块，Java中有PriorityQueue，C++则是priority_queue。

注意：虽然题目叫"吃苹果和队列"，但实际应该使用优先队列（堆）而不是普通队列。这是很多初学者容易混淆的点。

3. 详细解题步骤与代码实现

3.1 算法流程设计

  1. 初始化一个空堆和吃苹果计数res=0
  2. 遍历每一天i（从0到n-1）： a. 移除堆中所有已腐烂的苹果（保质期<=i） b. 如果当天有苹果(apples[i]>0)，将它们加入堆（存储保质期和数量） c. 尝试吃一个苹果（如果堆不为空）： i. 取出堆顶苹果（保质期最近的） ii. 如果数量>1，把剩余苹果放回堆 iii. res += 1
  3. 处理完n天后，可能堆中还有苹果： a. 只要堆不为空： i. 移除已腐烂苹果 ii. 如果还有苹果，吃一个并res+=1 iii. 当前天数i+=1（虚拟延长天数）

3.2 Python代码实现

import heapq def eatenApples(apples, days): heap = [] res = 0 n = len(apples) for i in range(n): # 移除过期苹果 while heap and heap[0][0] <= i: heapq.heappop(heap) # 加入新苹果 if apples[i] > 0: heapq.heappush(heap, [i + days[i], apples[i]]) # 吃一个苹果 if heap: res += 1 heap[0][1] -= 1 if heap[0][1] == 0: heapq.heappop(heap) # 处理剩余苹果 i = n while heap: while heap and heap[0][0] <= i: heapq.heappop(heap) if not heap: break res += 1 heap[0][1] -= 1 if heap[0][1] == 0: heapq.heappop(heap) i += 1 return res

3.3 关键代码解析

  1. 堆中存储的是[过期天数, 剩余数量]的列表，过期天数作为排序依据
  2. heapq.heappop(heap)会自动取出过期天数最小的苹果
  3. 吃苹果时只减少数量，只有当数量为0时才完全移除
  4. 第二个循环处理的是所有苹果都长出来后继续吃的情况

4. 复杂度分析与优化

4.1 时间复杂度

  • 外层循环O(n)天
  • 内层while循环总共会处理所有苹果，最多O(m)次（m是苹果总数）
  • 堆操作每次O(logk)，k是堆大小
  • 总体O(n logn)或O(m logn)，取决于哪个更大

4.2 空间复杂度

  • 堆最多存储O(n)天的苹果信息
  • 因此是O(n)

4.3 优化技巧

  1. 合并相同过期时间的苹果：可以在入堆前先用字典统计同一天过期的苹果总数，减少堆操作次数
  2. 提前终止：当堆中剩余苹果的总保质期天数小于剩余天数时，可以直接计算而不需要继续循环

优化后的部分代码：

from collections import defaultdict def eatenApples_optimized(apples, days): heap = [] res = 0 n = len(apples) day_dict = defaultdict(int) for i in range(n): # 合并相同过期时间的苹果 if apples[i] > 0: expiry = i + days[i] day_dict[expiry] += apples[i] # 加入堆（只处理新出现的过期时间） if i + days[i] not in heap_set: heapq.heappush(heap, i + days[i]) # ...其余部分类似...

5. 常见错误与调试技巧

5.1 典型错误案例

  1. 错误1：忘记处理n天之后的苹果

    • 症状：对于apples=[1,2,3], days=[5,2,1]返回3（正确应为7）
    • 解决方法：添加处理剩余苹果的循环

  2. 错误2：没有及时移除过期苹果

    • 症状：对于apples=[2], days=[1]返回2（正确应为1）
    • 解决方法：在吃苹果前先清理过期苹果

  3. 错误3：同一天多次吃苹果

    • 症状：对于apples=[3], days=[2]返回3（正确应为2）
    • 解决方法：每天最多吃一个苹果的限制

5.2 调试技巧

  1. 打印堆状态：在每次操作后打印堆内容，观察苹果数量和过期时间

    print(f"Day {i}: heap={heap}")

  2. 小数据测试：先用手算能验证的小数据测试，如：

    • apples=[1], days=[1] → 应返回1
    • apples=[0,1], days=[1,1] → 应返回1

  3. 边界测试：

    • 没有苹果的情况（apples=[]）
    • 苹果当天就腐烂的情况（days[i]=0）
    • 苹果永远不会腐烂的情况（days[i]很大）

6. 队列相关题目扩展

掌握了这道题后，可以尝试以下类似题目巩固优先队列的使用：

  1. LeetCode 703. 数据流中的第K大元素

    • 维护一个大小为K的最小堆

  2. LeetCode 253. 会议室II

    • 用堆管理会议室结束时间

  3. LeetCode 621. 任务调度器

    • 优先处理剩余次数最多的任务

  4. LeetCode 767. 重构字符串

    • 每次取剩余最多的两个不同字符

对于想深入理解队列的读者，建议实际实现一个优先队列。以下是简易版实现思路：

class PriorityQueue: def __init__(self): self.heap = [] def push(self, item, priority): heapq.heappush(self.heap, (priority, item)) def pop(self): return heapq.heappop(self.heap)[1] def peek(self): return self.heap[0][1] def __len__(self): return len(self.heap)

在实际工程中，消息队列（如Kafka、RabbitMQ）的消息优先级实现原理与此类似，都是基于堆结构来管理消息的优先级。