在一條環(huán)路上有 N 個(gè)加油站，其中第 i 個(gè)加油站有汽油 gas[i] 升椭更。你有一輛油箱容量無限的的汽車，從第 i 個(gè)加油站開往第 i+1 個(gè)加油站需要消耗汽油 cost[i] 升。你從其中的一個(gè)加油站出發(fā)京腥，開始時(shí)油箱為空鲸郊。如果你可以繞環(huán)路行駛一周丰榴，則返回出發(fā)時(shí)加油站的編號，否則返回 -1

https://leetcode-cn.com/problems/gas-station/

示例1：

輸入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

輸出: 3

解釋:
從 3 號加油站(索引為 3 處)出發(fā)秆撮，可獲得 4 升汽油四濒。此時(shí)油箱有 = 0 + 4 = 4 升汽油
開往 4 號加油站，此時(shí)油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號加油站职辨，此時(shí)油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號加油站盗蟆，此時(shí)油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號加油站，此時(shí)油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號加油站舒裤，你需要消耗 5 升汽油喳资，正好足夠你返回到 3 號加油站。
因此腾供，3 可為起始索引仆邓。

示例2：

輸入:
gas = [2,3,4]
cost = [3,4,3]

輸出: -1

解釋:
你不能從 0 號或 1 號加油站出發(fā)，因?yàn)闆]有足夠的汽油可以讓你行駛到下一個(gè)加油站伴鳖。
我們從 2 號加油站出發(fā)节值，可以獲得 4 升汽油。 此時(shí)油箱有 = 0 + 4 = 4 升汽油
開往 0 號加油站榜聂，此時(shí)油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號加油站搞疗，此時(shí)油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號加油站，因?yàn)榉党绦枰?4 升汽油须肆，但是你的油箱只有 3 升汽油匿乃。
因此，無論怎樣休吠，你都不可能繞環(huán)路行駛一周扳埂。

提示：

如果題目有解，該答案即為唯一答案瘤礁。
輸入數(shù)組均為非空數(shù)組阳懂，且長度相同。
輸入數(shù)組中的元素均為非負(fù)數(shù)。

Java解法

思路：

• 雖然不限起點(diǎn)岩调，但方向是有固定的 從i 到i+1巷燥，主要思路分兩步
  • 遍歷每一個(gè)起點(diǎn)
  • 判斷當(dāng)前出發(fā)是否滿足到達(dá)
• 完成解法，但效率不是很好

package sj.shimmer.algorithm.m4_2021;

/**
 * Created by SJ on 2021/4/6.
 */

class D69 {
    public static void main(String[] args) {
        System.out.println(canCompleteCircuit(new int[]{1,2,3,4,5},new int[]{3,4,5,1,2}));
        System.out.println(canCompleteCircuit(new int[]{2,3,4},new int[]{3,4,3}));
    }
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int start = 0;
        while (start < gas.length) {
            if (go(start,gas,cost)>=0) {
                return start;
            }
            start++;
        }
        return -1;
    }
    public static int go(int start,int[] gas, int[] cost) {
        int length = gas.length;
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum +=gas[start]-cost[start];
            if (sum<0) {
                return -1;
            }
            start++;
            if (start>=length) {
                start = 0;
            }
        }
        return sum;
    }
}

image

官方解

https://leetcode-cn.com/problems/gas-station/solution/jia-you-zhan-by-leetcode-solution/

1. 一次遍歷

   以我的思路為基礎(chǔ)進(jìn)行的優(yōu)化

   （官方解利用不等式計(jì)算出的關(guān)系）優(yōu)化基礎(chǔ)是如果x出發(fā)号枕，不能到達(dá)y的下一站缰揪，那么說明，x到y(tǒng)之間的所有加油站都無法到達(dá)(因?yàn)榈竭_(dá)的前提是有油或者為0葱淳，y不能到y(tǒng)+1钝腺，前面所有累加油都不夠，那部分累加油自然更加不夠)

   這樣就可以省去大量的不必要計(jì)算

   參考寫法

   public  int canCompleteCircuit(int[] gas, int[] cost) {
       int length = gas.length;
       int start = 0;
       while (start<length) {
           int arrive = 0;
           int sum = 0;
           while (arrive<length){
               int index = (start + arrive) % length;
               sum +=gas[index]-cost[index];
               if (sum<0) {
                   break;
               }
               arrive++;
           }
           if (arrive==length) {
               return start;
           }else {
               start = start+arrive+1;
           }
       }
       return -1;
   }
   

   image

   • 時(shí)間復(fù)雜度：O(N)

   • 空間復(fù)雜度：O(1)