LeetCode100天Day18-加油站与分发糖果贪心算法与双向遍历摘要本文详细解析了LeetCode中两道经典题目——“加油站和分发糖果”。通过贪心策略寻找可以环绕一周的起点以及使用双向遍历解决分发糖果问题帮助读者掌握贪心算法的应用和双向扫描的技巧。目录文章目录LeetCode100天Day18-加油站与分发糖果贪心算法与双向遍历目录1. 加油站Gas Station1.1 题目描述1.2 解题思路1.3 代码实现1.4 代码逐行解释第一部分初始化第二部分尝试每个起点第三部分返回结果1.5 执行流程详解1.6 算法图解1.7 复杂度分析1.8 边界情况2. 分发糖果Candy2.1 题目描述2.2 解题思路2.3 代码实现2.4 代码逐行解释第一部分初始化第二部分从左向右遍历第三部分从右向左遍历第四部分累加糖果2.5 执行流程详解2.6 算法图解2.7 复杂度分析2.8 边界情况3. 两题对比与总结3.1 算法对比3.2 贪心策略3.3 双向遍历模板3.4 环路处理技巧4. 总结参考资源文章标签1. 加油站Gas Station1.1 题目描述在一条环路上有n个加油站其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的的汽车从第i个加油站开往第i1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发开始时油箱为空。给定两个整数数组gas和cost如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回-1。如果存在解则保证它是唯一的。示例 1输入: gas [1,2,3,4,5], cost [3,4,5,1,2] 输出: 3 解释: 从3号加油站(索引为3处)出发可获得4升汽油。此时油箱有 0 4 4升汽油 开往4号加油站此时油箱有4 - 1 5 8升汽油 开往0号加油站此时油箱有8 - 2 1 7升汽油 开往1号加油站此时油箱有7 - 3 2 6升汽油 开往2号加油站此时油箱有6 - 4 3 5升汽油 开往3号加油站你需要消耗5升汽油正好足够你返回到3号加油站。 因此3可为起始索引。示例 2输入: gas [2,3,4], cost [3,4,3] 输出: -1 解释你不能从0号或1号加油站出发因为没有足够的汽油可以让你行驶到下一个加油站。 我们从2号加油站出发可以获得4升汽油。此时油箱有 0 4 4升汽油 开往0号加油站此时油箱有4 - 3 2 3升汽油 开往1号加油站此时油箱有3 - 3 3 3升汽油 你无法返回2号加油站因为返程需要消耗4升汽油但你的油箱只有3升汽油。 因此无论怎样你都不可能绕环路行驶一周。1.2 解题思路这道题使用贪心算法从每个加油站出发模拟环绕一周的过程如果油量不足则从下一个位置重新开始如果总油量大于等于总消耗则一定有解解题步骤初始化index为0表示从第一个加油站开始尝试循环尝试每个起点模拟从该点出发环绕n个加油站如果油量不足更新index为失败位置的下一位如果成功环绕一周返回起点1.3 代码实现classSolution{publicintcanCompleteCircuit(int[]gas,int[]cost){inttotal0;intindex0;intlengas.length;while(indexlen){booleanflagtrue;intgas_temp0;for(intiindex;ilenindex;i){intnow_indexi%len;gas_tempgas_tempgas[now_index]-cost[now_index];if(gas_temp0){flagfalse;indexi1;break;}}if(flagtrue){returnindex;}}return-1;}}1.4 代码逐行解释第一部分初始化inttotal0;intindex0;intlengas.length;变量说明变量初始值含义total0未使用index0当前尝试的起点lengas.length加油站数量第二部分尝试每个起点while(indexlen){booleanflagtrue;intgas_temp0;for(intiindex;ilenindex;i){intnow_indexi%len;gas_tempgas_tempgas[now_index]-cost[now_index];if(gas_temp0){flagfalse;indexi1;break;}}if(flagtrue){returnindex;}}外层循环while(indexlen)条件说明index len还有起点可以尝试内层循环for(intiindex;ilenindex;i)变量说明i当前访问的加油站索引未取模len index从index开始访问n个加油站索引映射intnow_indexi%len;inow_index说明00第1个站11第2个站n-1n-1第n个站n0回到第1个站油量计算gas_tempgas_tempgas[now_index]-cost[now_index];操作说明gas_temp gas[now_index]加油- cost[now_index]消耗失败处理if(gas_temp0){flagfalse;indexi1;break;}操作说明gas_temp 0油量不足无法继续index i 1从失败位置的下一位重新开始第三部分返回结果if(flagtrue){returnindex;}条件返回值说明flag trueindex可以环绕一周否-1无法环绕1.5 执行流程详解示例1gas [1,2,3,4,5], cost [3,4,5,1,2]初始状态 gas [1, 2, 3, 4, 5] cost [3, 4, 5, 1, 2] len 5 index 0 第1次尝试从index0开始 gas_temp 0 i0: now_index0 gas_temp 0 1 - 3 -2 -2 0? 是失败 index 0 1 1 退出内层循环 第2次尝试从index1开始 gas_temp 0 i1: now_index1 gas_temp 0 2 - 4 -2 -2 0? 是失败 index 1 1 2 退出内层循环 第3次尝试从index2开始 gas_temp 0 i2: now_index2 gas_temp 0 3 - 5 -2 -2 0? 是失败 index 2 1 3 退出内层循环 第4次尝试从index3开始 gas_temp 0 i3: now_index3 gas_temp 0 4 - 1 3 i4: now_index4 gas_temp 3 5 - 2 6 i5: now_index0 gas_temp 6 1 - 3 4 i6: now_index1 gas_temp 4 2 - 4 2 i7: now_index2 gas_temp 2 3 - 5 0 内层循环结束flag true 返回 index 3 输出: 3示例2gas [2,3,4], cost [3,4,3]初始状态 gas [2, 3, 4] cost [3, 4, 3] len 3 index 0 第1次尝试从index0开始 gas_temp 0 i0: now_index0 gas_temp 0 2 - 3 -1 -1 0? 是失败 index 0 1 1 退出内层循环 第2次尝试从index1开始 gas_temp 0 i1: now_index1 gas_temp 0 3 - 4 -1 -1 0? 是失败 index 1 1 2 退出内层循环 第3次尝试从index2开始 gas_temp 0 i2: now_index2 gas_temp 0 4 - 3 1 i3: now_index0 gas_temp 1 2 - 3 0 i4: now_index1 gas_temp 0 3 - 4 -1 -1 0? 是失败 index 4 1 5 退出内层循环 index5, 5 3? 否退出外层循环 返回 -1 输出: -11.6 算法图解gas [1, 2, 3, 4, 5] cost [3, 4, 5, 1, 2] 净值: [-2, -2, -2, 3, 3] 尝试从0出发 位置0: 0 1 - 3 -2 0失败 尝试从1出发 位置1: 0 2 - 4 -2 0失败 尝试从2出发 位置2: 0 3 - 5 -2 0失败 尝试从3出发 位置3: 0 4 - 1 3 位置4: 3 5 - 2 6 位置0: 6 1 - 3 4 位置1: 4 2 - 4 2 位置2: 2 3 - 5 0 环绕一周成功 起点: 31.7 复杂度分析分析维度复杂度说明时间复杂度O(n²)最坏情况尝试所有起点空间复杂度O(1)只使用常数空间优化思路一次遍历O(n)// 优化版本一次遍历classSolution{publicintcanCompleteCircuit(int[]gas,int[]cost){intngas.length;inttotalSurplus0;intsurplus0;intstart0;for(inti0;in;i){totalSurplusgas[i]-cost[i];surplusgas[i]-cost[i];if(surplus0){starti1;surplus0;}}returntotalSurplus0?start:-1;}}1.8 边界情况gascost说明输出[1][1]单个站0[1][2]无法出发-1[2][1]可以出发02. 分发糖果Candy2.1 题目描述n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下要求给这些孩子分发糖果每个孩子至少分配到1个糖果。相邻两个孩子中评分更高的那个会获得更多的糖果。请你给每个孩子分发糖果计算并返回需要准备的最少糖果数目。示例 1输入ratings [1,0,2] 输出5 解释你可以分别给第一个、第二个、第三个孩子分发2、1、2颗糖果。示例 2输入ratings [1,2,2] 输出4 解释你可以分别给第一个、第二个、第三个孩子分发1、2、1颗糖果。 第三个孩子只得到1颗糖果这满足题面中的两个条件。2.2 解题思路这道题使用双向遍历的方法初始化每个孩子1颗糖果从左向右遍历如果右边孩子评分更高则增加糖果从右向左遍历如果左边孩子评分更高则增加糖果返回总糖果数解题步骤创建arr数组初始化为1从左向右遍历处理递增序列从右向左遍历处理递减序列累加糖果数2.3 代码实现classSolution{publicintcandy(int[]ratings){intlenratings.length;int[]arrnewint[len];for(inti0;ilen;i){arr[i]1;}for(inti1;ilen;i){if(ratings[i]ratings[i-1]){arr[i]arr[i-1]1;}}for(intilen-2;i0;i--){if(ratings[i]ratings[i1]){arr[i]Math.max(arr[i],arr[i1]1);}}inttemp0;for(inti0;ilen;i){temparr[i];}returntemp;}}2.4 代码逐行解释第一部分初始化intlenratings.length;int[]arrnewint[len];for(inti0;ilen;i){arr[i]1;}功能初始化糖果数组变量说明len孩子数量arr糖果数组初始值全为1第二部分从左向右遍历for(inti1;ilen;i){if(ratings[i]ratings[i-1]){arr[i]arr[i-1]1;}}逻辑如果右边孩子评分更高糖果左边孩子糖果1条件操作ratings[i] ratings[i-1]右边评分更高arr[i] arr[i-1] 1右边糖果更多示例ratings [1, 0, 2] arr [1, 1, 1] i1: ratings[1]0, ratings[0]1 0 1? 否 i2: ratings[2]2, ratings[1]0 2 0? 是 arr[2] arr[1] 1 1 1 2 arr [1, 1, 2]第三部分从右向左遍历for(intilen-2;i0;i--){if(ratings[i]ratings[i1]){arr[i]Math.max(arr[i],arr[i1]1);}}逻辑如果左边孩子评分更高糖果max(当前糖果, 右边孩子糖果1)条件操作ratings[i] ratings[i1]左边评分更高arr[i] max(arr[i], arr[i1]1)取最大值保证两边都满足为什么要用max第一次遍历后arr [1, 1, 2] 如果ratings [2, 1, 0] 从左向右 arr [1, 1, 1] (没有递增) 从右向左 i1: ratings[1]1 ratings[2]0 arr[1] max(1, arr[2]1) max(1, 2) 2 i0: ratings[0]2 ratings[1]1 arr[0] max(1, arr[1]1) max(1, 3) 3 arr [3, 2, 1] 如果不取max arr [2, 2, 1] (左边只有1颗违反规则)第四部分累加糖果inttemp0;for(inti0;ilen;i){temparr[i];}returntemp;2.5 执行流程详解示例1ratings [1,0,2]初始状态 ratings [1, 0, 2] arr [1, 1, 1] 步骤1从左向右 i1: ratings[1]0 ratings[0]1? 否 i2: ratings[2]2 ratings[1]0? 是 arr[2] arr[1] 1 2 arr [1, 1, 2] 步骤2从右向左 i1: ratings[1]0 ratings[2]2? 否 i0: ratings[0]1 ratings[1]0? 是 arr[0] max(1, arr[1]1) max(1, 2) 2 arr [2, 1, 2] 步骤3累加 temp 2 1 2 5 输出: 5示例2ratings [1,2,2]初始状态 ratings [1, 2, 2] arr [1, 1, 1] 步骤1从左向右 i1: ratings[1]2 ratings[0]1? 是 arr[1] 2 i2: ratings[2]2 ratings[1]2? 否 arr [1, 2, 1] 步骤2从右向左 i1: ratings[1]2 ratings[2]2? 否 i0: ratings[0]1 ratings[1]2? 否 arr [1, 2, 1] 步骤3累加 temp 1 2 1 4 输出: 42.6 算法图解ratings [1, 0, 2] 初始化[1, 1, 1] 从左向右 1 → 0: 不递增 0 → 2: 递增arr[2] arr[1] 1 2 arr [1, 1, 2] 从右向左 2 → 0: 不递增 0 → 1: 递增arr[0] max(1, arr[1]1) 2 arr [2, 1, 2] 验证 位置0: 2颗位置1: 1颗 ✓ (1 0, 2 1) 位置1: 1颗位置2: 2颗 ✓ (2 0, 2 1) 总糖果: 2 1 2 52.7 复杂度分析分析维度复杂度说明时间复杂度O(n)三次遍历空间复杂度O(n)糖果数组2.8 边界情况ratings说明输出[1]单个孩子1[1,2]递增3[2,1]递减3[1,1,1]全相同33. 两题对比与总结3.1 算法对比对比项加油站分发糖果核心算法贪心双向遍历数据结构数组数组时间复杂度O(n²)O(n)空间复杂度O(1)O(n)应用场景环路问题分配问题3.2 贪心策略加油站贪心// 从失败位置的下一位重新开始if(gas_temp0){indexi1;break;}分发糖果贪心// 从左向右递增序列if(ratings[i]ratings[i-1]){arr[i]arr[i-1]1;}// 从右向左保证左边规则if(ratings[i]ratings[i1]){arr[i]Math.max(arr[i],arr[i1]1);}3.3 双向遍历模板// 双向遍历模板// 第一次遍历处理一个方向for(inti1;in;i){if(满足条件){result[i]result[i-1]1;}}// 第二次遍历处理另一个方向for(intin-2;i0;i--){if(满足条件){result[i]Math.max(result[i],result[i1]1);}}3.4 环路处理技巧// 环路索引映射for(intistart;istartn;i){intindexi%n;// 映射到[0, n-1]// 处理}4. 总结今天我们学习了两道贪心算法题目加油站掌握贪心策略寻找可行起点理解环路问题的处理分发糖果掌握双向遍历理解两边约束的处理方法核心收获贪心算法需要证明局部最优导致全局最优环路问题可以用取模运算处理双向遍历可以处理双边约束Math.max确保两边规则都满足失败后可以跳过不可能的位置练习建议用一次遍历优化加油站问题思考如何用O(1)空间解决分发糖果学习其他贪心算法题目参考资源LeetCode 中国站 - 加油站LeetCode 中国站 - 分发糖果贪心算法详解双向遍历技巧文章标签#LeetCode #算法 #Java #贪心算法 #数组喜欢这篇文章吗别忘了点赞、收藏和分享你的支持是我创作的最大动力