是否可以从某点开始加油站的循环

前提知识：获得窗口滑动过程中的最大值列表

【6 4 2 3 5 7 0 5】 这样的一序列数（数组arr），求窗口滑动过程中的最大值列表。

way：

用一个双端队列，L初始指向0位置，将元素从右边队尾入队，如果队列为空或当前元素比队尾元素小，从队尾入队 ，否则，让队列尾部比当前元素小的元素都出来，将当前元素从尾部入队（在队列尾部维护一个严格的从大到小的数据列），受窗口大小限制，L向右移动一格让左侧元素出窗口，左指针右移时，对应队列中的值从左边出队（队列中放的是数组的下标），go on，在这个过程中，L指针指向的值就是当前窗口内的最大值。

题目描述：在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。134. 加油站 - 力扣（LeetCode）

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

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

示例：

可以看成下面这样。

way：

gas:    1 2 3 4 5

cos:     3 4 5 1 2

g-c:     -2 -2 -2 3 3 （g-c的意思是离开当前点，去到下一个点还没加油的油量 ）

(g-c) * 2:      -2 -2 -2 3 3 -2 -2 -2 3 3

前缀和         -2 -4 -6 -3 0 -2 -4 -6 -3 0

从2位置开始的耗油： -2 -4 -1 2 0 在前缀和中可以通过 （-4 -6 -3 0 -2) - (-2)获得

从2位置出发，能不能到绕一圈再回到2 看从2位置开始的耗油里有没有<0的，如果有，就到不了

然后前缀和数组是我们用于计算的数组，我们只要用滑动窗口中的最小值-(窗口最左位置左边的一个值) 获得这个窗口最小的耗油，看这个最小耗油是不是<0，就能判断从窗口最左位置能不能绕一圈回来了，如果<0就不能，如果>=0，就说明可以从窗口最左边的位置开始绕圈且不会熄火。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        vector<int>result = goodArray(gas, cost);
        if(result.size() >  0)
        {
            return result[0];
        }
        return -1;
    }


    vector<int> goodArray(vector<int>gas, vector<int>cost)
    {
        int N = gas.size();
        int M = N*2;

        //放置可以从某个下标开始的们
        vector<int>result;
        vector<int>arr(M);

        //double
        for(int i=0; i<N; i++)
        {
            arr[i] = gas[i]-cost[i];
            arr[i+N] = gas[i]-cost[i];
        }


        //前缀和
        for(int i=1; i<M; i++)
        {
            arr[i]=arr[i-1]+arr[i];
        }

        deque<int>que;
        int index=0;
        int w=N;

        for(int R=0; R<M; R++)
        {
            while(!que.empty() && arr[que.back()] >= arr[R])
            {
                que.pop_back();
            }
            que.push_back(R);


            int leftVal = R-w>=0?arr[R-w]:0 ;

            if(que.front() == R-w )
            {
                que.pop_front();
            }

            if(R >= w-1)
            {
                cout<<arr[que.front()]<<" "<<leftVal<<endl;
                if(arr[que.front()] - leftVal >= 0)
                {
                    result.push_back(R-w+1);
                }
            }
        }

        return result;
    }

};

放一下LT（a people）的写法， i是窗口的左边界，j是窗口的右边界+1。

public class GasStation {

	// 这个方法的时间复杂度O(N)，额外空间复杂度O(N)
	public static int canCompleteCircuit(int[] gas, int[] cost) {
		boolean[] good = goodArray(gas, cost);
		for (int i = 0; i < gas.length; i++) {
			if (good[i]) {
				return i;
			}
		}
		return -1;
	}

	public static boolean[] goodArray(int[] g, int[] c) {
		int N = g.length;
		int M = N << 1;
		int[] arr = new int[M];
		for (int i = 0; i < N; i++) {
			arr[i] = g[i] - c[i];
			arr[i + N] = g[i] - c[i];
		}
		for (int i = 1; i < M; i++) {
			arr[i] += arr[i - 1];
		}
		LinkedList<Integer> w = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			while (!w.isEmpty() && arr[w.peekLast()] >= arr[i]) {
				w.pollLast();
			}
			w.addLast(i);
		}
		boolean[] ans = new boolean[N];
		for (int offset = 0, i = 0, j = N; j < M; offset = arr[i++], j++) {
			if (arr[w.peekFirst()] - offset >= 0) {
				ans[i] = true;
			}
			if (w.peekFirst() == i) {
				w.pollFirst();
			}
			while (!w.isEmpty() && arr[w.peekLast()] >= arr[j]) {
				w.pollLast();
			}
			w.addLast(j);
		}
		return ans;
	}

}