1. 项目概述LeetCode吃苹果问题与队列应用这道来自LeetCode的编程题编号为1705题目描述如下有一棵特殊的苹果树一连n天每天都会长出若干个苹果。在第i天树上会长出apples[i]个苹果这些苹果会在days[i]天后腐烂即第i天长的苹果在第idays[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中有PriorityQueueC则是priority_queue。注意虽然题目叫吃苹果和队列但实际应该使用优先队列堆而不是普通队列。这是很多初学者容易混淆的点。3. 详细解题步骤与代码实现3.1 算法流程设计初始化一个空堆和吃苹果计数res0遍历每一天i从0到n-1 a. 移除堆中所有已腐烂的苹果保质期i b. 如果当天有苹果(apples[i]0)将它们加入堆存储保质期和数量 c. 尝试吃一个苹果如果堆不为空 i. 取出堆顶苹果保质期最近的 ii. 如果数量1把剩余苹果放回堆 iii. res 1处理完n天后可能堆中还有苹果 a. 只要堆不为空 i. 移除已腐烂苹果 ii. 如果还有苹果吃一个并res1 iii. 当前天数i1虚拟延长天数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 res3.3 关键代码解析堆中存储的是[过期天数, 剩余数量]的列表过期天数作为排序依据heapq.heappop(heap)会自动取出过期天数最小的苹果吃苹果时只减少数量只有当数量为0时才完全移除第二个循环处理的是所有苹果都长出来后继续吃的情况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 优化技巧合并相同过期时间的苹果可以在入堆前先用字典统计同一天过期的苹果总数减少堆操作次数提前终止当堆中剩余苹果的总保质期天数小于剩余天数时可以直接计算而不需要继续循环优化后的部分代码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忘记处理n天之后的苹果症状对于apples[1,2,3], days[5,2,1]返回3正确应为7解决方法添加处理剩余苹果的循环错误2没有及时移除过期苹果症状对于apples[2], days[1]返回2正确应为1解决方法在吃苹果前先清理过期苹果错误3同一天多次吃苹果症状对于apples[3], days[2]返回3正确应为2解决方法每天最多吃一个苹果的限制5.2 调试技巧打印堆状态在每次操作后打印堆内容观察苹果数量和过期时间print(fDay {i}: heap{heap})小数据测试先用手算能验证的小数据测试如apples[1], days[1] → 应返回1apples[0,1], days[1,1] → 应返回1边界测试没有苹果的情况apples[]苹果当天就腐烂的情况days[i]0苹果永远不会腐烂的情况days[i]很大6. 队列相关题目扩展掌握了这道题后可以尝试以下类似题目巩固优先队列的使用LeetCode 703. 数据流中的第K大元素维护一个大小为K的最小堆LeetCode 253. 会议室II用堆管理会议室结束时间LeetCode 621. 任务调度器优先处理剩余次数最多的任务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的消息优先级实现原理与此类似都是基于堆结构来管理消息的优先级。 
长河君 · 2026/10/24 6:54:56 · 阅读 1.2k LeetCode吃苹果问题解析：优先队列的贪心算法应用
1. 项目概述LeetCode吃苹果问题与队列应用这道来自LeetCode的编程题编号为1705题目描述如下有一棵特殊的苹果树一连n天每天都会长出若干个苹果。在第i天树上会长出apples[i]个苹果这些苹果会在days[i]天后腐烂即第i天长的苹果在第idays[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中有PriorityQueueC则是priority_queue。注意虽然题目叫吃苹果和队列但实际应该使用优先队列堆而不是普通队列。这是很多初学者容易混淆的点。3. 详细解题步骤与代码实现3.1 算法流程设计初始化一个空堆和吃苹果计数res0遍历每一天i从0到n-1 a. 移除堆中所有已腐烂的苹果保质期i b. 如果当天有苹果(apples[i]0)将它们加入堆存储保质期和数量 c. 尝试吃一个苹果如果堆不为空 i. 取出堆顶苹果保质期最近的 ii. 如果数量1把剩余苹果放回堆 iii. res 1处理完n天后可能堆中还有苹果 a. 只要堆不为空 i. 移除已腐烂苹果 ii. 如果还有苹果吃一个并res1 iii. 当前天数i1虚拟延长天数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 res3.3 关键代码解析堆中存储的是[过期天数, 剩余数量]的列表过期天数作为排序依据heapq.heappop(heap)会自动取出过期天数最小的苹果吃苹果时只减少数量只有当数量为0时才完全移除第二个循环处理的是所有苹果都长出来后继续吃的情况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 优化技巧合并相同过期时间的苹果可以在入堆前先用字典统计同一天过期的苹果总数减少堆操作次数提前终止当堆中剩余苹果的总保质期天数小于剩余天数时可以直接计算而不需要继续循环优化后的部分代码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忘记处理n天之后的苹果症状对于apples[1,2,3], days[5,2,1]返回3正确应为7解决方法添加处理剩余苹果的循环错误2没有及时移除过期苹果症状对于apples[2], days[1]返回2正确应为1解决方法在吃苹果前先清理过期苹果错误3同一天多次吃苹果症状对于apples[3], days[2]返回3正确应为2解决方法每天最多吃一个苹果的限制5.2 调试技巧打印堆状态在每次操作后打印堆内容观察苹果数量和过期时间print(fDay {i}: heap{heap})小数据测试先用手算能验证的小数据测试如apples[1], days[1] → 应返回1apples[0,1], days[1,1] → 应返回1边界测试没有苹果的情况apples[]苹果当天就腐烂的情况days[i]0苹果永远不会腐烂的情况days[i]很大6. 队列相关题目扩展掌握了这道题后可以尝试以下类似题目巩固优先队列的使用LeetCode 703. 数据流中的第K大元素维护一个大小为K的最小堆LeetCode 253. 会议室II用堆管理会议室结束时间LeetCode 621. 任务调度器优先处理剩余次数最多的任务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的消息优先级实现原理与此类似都是基于堆结构来管理消息的优先级。