贪心算法求解加油站问题
代码随想录链接:代码随想录
思路:
首先构造一个差距数组diff，其中每个位置的值都是gas数组和cost数组对应位置的值的差
初始化一个变量start记录从哪个加油站出发，一个变量cursum记录从start出发时车内油量的总和，一个变量totsum表示整个差距数组diff的元素之和
依次遍历差距数组中的每个元素，每遍历一个就更新cursum和totsum，之后判断cursum是否小于0，如果小于0则表示从start出发无法遍历全部的加油站，同时置start为i+1以及将cursum置于0
遍历完毕全部的元素之后，判断totsum是否小于0，如果小于0表示无法找到合适的出发位置能够遍历整个数组，此时返回-1，否则变量start表示的便是能够出发遍历全部加油站的起始位置，将其返回即可
对应代码:
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int index = 0;
for (int i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) {
index = (i + 1) % gas.length ;
curSum = 0;
}
}
if (totalSum < 0) return -1;
return index;
}
}