刷题笔记:力扣第134题-加油站

1.拿到题目想到本题应该是在“gas[i] – cost[i]”即净赚汽油上做文章所以尝试使用滑动窗口方法不断向右移动右边界cur。当窗口内的净赚汽油总和大于0时说明能到达该处如果小于0则不断收缩左边界start直到总和大于0。同时维护已经途径的加油站个数step当step gasSize时说明找到了答案如果cur已经到达数组末尾但还没有满足条件的step则说明无解。2.基于以上思想写出的完整代码如下1. int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) { 2. // start候选起点下标 3. int start 0; 4. // cur当前遍历到的站点指针 5. int cur 0; 6. // sum当前区间内剩余油量总和 7. int sum 0; 8. // step当前区间包含的站点数量 9. int step 0; 10. 11. // 候选起点不超过总站数时循环 12. while (start gasSize){ 13. // 计算当前站点加油减耗油的净油量 14. int tmp gas[cur % gasSize] - cost[cur % costSize]; 15. sum tmp; 16. // 前进到下一站 17. cur; 18. step; 19. 20. // 当前区间油量不足不断抛弃起点站点直到sum0或区间无站点 21. while (sum 0 step 0){ 22. sum - gas[start % gasSize] - cost[start % costSize]; 23. start; 24. step--; 25. } 26. 27. // 区间站点数量等于总站数说明成功绕环一周返回起点 28. if (step gasSize) return start; 29. } 30. 31. // 所有起点均无法完成环路返回-1 32. return -1; 33. }该算法时间复杂度为O(n)空间复杂度为O(1)。3.在使用滑动窗口的时候遇到了如下细节问题1一开始错误地认为净赚汽油为gas[cur % gasSize] - cost[(cur gasSize - 1) % costSize]原因是看到官方题目示例中的一加一减就是错位的但没有考虑该示例一开始就单独加上了出发地的获取汽油数并在最后单独减去了到达该处的所需汽油数所以真正的周期还是gas[cur % gasSize] - cost[cur % costSize]即当前加油站能获取的汽油数减去到达当前加油站的所需汽油数。2收缩左边界start应该放在while循环中而不是if中因为本题滑动窗口的逻辑需要内部总和大于0时再扩张右边界cur只if判断一次、收缩左边界start一次无法保证内部总和大于0。