2025-3-14 leetcode刷题情况（贪心算法）

一、53.最大子序和

1.题目描述

2.代码

3.思路

先特殊处理数组只有一个数的情况，再定义两个变量，sum用于记录最大子数组和，count用于记录当前连续子数组的和。使用for循环遍历数组nums中的每个元素。对于每个元素nums[i]，将其累加到count中。每次累加后，使用Math.max函数比较sum和count的大小，将较大值更新到sum中，确保sum始终记录最大子数组和。如果count小于等于 0，说明当前连续子数组的和为负数或 0，继续往后累加这个子数组不会得到更大的和，因此将count重置为 0，重新开始计算新的连续子数组和。遍历结束后，sum中存储的就是最大子数组和，将其返回。

二、134.加油站

1.题目描述

2.代码

3.思路

1. 变量初始化：
   • curSum：用于记录从当前起始加油站出发，到当前遍历到的加油站时，剩余的汽油量。初始化为 0。
   • totalSum：用于记录整个环形路线中，汽油总量与消耗总量的差值。初始化为 0。
   • index：用于记录可能的起始加油站的索引，初始化为 0。
2. 遍历加油站：
   • 使用 for 循环遍历每个加油站，索引为 i。
   • 对于每个加油站，计算在该加油站补充汽油并前往下一个加油站后的剩余汽油量，即 gas[i] - cost[i]，将其累加到 curSum 和 totalSum 中。
   • 如果 curSum 小于 0，说明从当前起始加油站出发无法到达当前加油站，需要更换起始加油站。将起始加油站的索引更新为 (i + 1) % gas.length，并将 curSum 重置为 0，重新开始计算剩余汽油量。
3. 判断是否能完成一圈行驶：
   • 遍历结束后，检查 totalSum 的值。如果 totalSum 小于 0，说明整个环形路线上的汽油总量小于消耗总量，无论从哪个加油站出发都无法完成一圈行驶，返回 -1。
   • 如果 totalSum 大于等于 0，说明存在可以完成一圈行驶的起始加油站，返回 index。