leetcode做题笔记134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

思路一：贪心

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
   int profile[gasSize];
   int start = 0,sum = 0;
    for(int i = 0;i
        profile[i] = gas[i] - cost[i];
        if(profile[i]>profile[start])start = i;
        sum+=profile[i];
    }
    if(sum<0)return -1;
 
    return start;
    
}

分析：

本题分析题意，即找到一条路径使总和大于耗油量即可，利用for循环，列举每个站点到结尾的情况，当profile[i]>profile[start]即初始油量最大时可从此开始，不满足到达终点的情况则返回-1

总结：

本题考察贪心的应用，不断向后判断是否补给油量大于当前油量，最后判断总和是否大于耗油量，返回开始的位置