加油站的良好出发点

1、题目

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

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

给定两个整数数组 gas 和 cost ，返回从每个加油站出发是否能行驶一周的数组。

例子：

输入：gas = [1,1,3,1]，cost = [2,2,1,1]
输出：[F,F,T,F]
解释：从第3个加油站出发可以回到该出发点，而其他加油站出发则不行。
1
2
3

【Leetcode134：加油站】是本题的阉割版。

2、思路

先对两个数组进行处理， gas - cost ，得到数组 arr = [-1, -1, 2, 0]，该数组从某个位置开始累加和小于 0，则不能行驶一周。

暴力解法：

从每个位置出发，遍历一遍数组arr，得到的结果如果 >0 ，就是能行驶一周，否则表示不能。即循环数组的遍历，时间复杂度 $O(n^2)$。

优化：

对 arr 数组求累加和（前缀和）数组，假设 arr = [-2, -3, 4, -2, 6, -1]，则 sum = [-2，-5，-1， -3， 3，2，0，-3， 1， -1， 5，4]。

从 0 位置出发的累加和数组为 [-2, -5, -1, -3, 3, 2]，因为数组中出现了小于 0 的数或者说该数组中的最小值-5 < 0，所以知道从 0 位置出发不行；

从 1 位置出发的累加和数组为 [-3, 1, -1, 5, 4, 2]，而该数组就是 sum[1] - sum[0]、sum[2] - sum[0] 、sum[3] - sum[0]、sum[4] - sum[0] 、sum[5] - sum[0] 以及 sum[6] - sum[0] 得到的。

sum[0...5] 中的最小值 -5，还原到原始数组的最小值就是 -5 - 0 = -5；而 sum[1...6] 中的最小值 -5，还原到原始的最小值是 -5 - (-2) = -3 < 0，所以无法从 1 位置出发环形一周。

就是说找到窗口中的最小值，进行加工得到的结果如果小于 0，则说明从该窗口的其实位置出发是无法走完全程的。

• C++ 版

class Solution {
private:
    bool *goodArray(vector<int> &gas, vector<int> &cost) {
        int n = gas.size();
        int m = n << 1;
        int arr[m];

        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];
        }

        deque<int> w;
        for (int i = 0; i < n; i++) {
            while (!w.empty() && arr[w.back()] >= arr[i]) {
                w.pop_back();
            }
            w.push_back(i);
        }

        
        bool ans[n];
        memset(ans, 0, sizeof(ans));

        for (int offset = 0, i = 0, j = n; j < m; offset = arr[i++], j++) {
            if (arr[w.front()] - offset >= 0) {
                ans[i] = true;
            }

            if (w.front() == i) {
                w.pop_front();
            }

            while (!w.empty() && arr[w.back()] >= arr[j]) {
                w.pop_back();
            }
            w.push_back(j);
        }

        return ans;
    }
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        bool *good = goodArray(gas, cost);
        for (int i = 0; i < gas.size(); i++) {
            if (good[i]) {
                return i;
            }
        }

        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

• Java 版

import java.util.LinkedList;

// 测试链接：https://leetcode.com/problems/gas-station
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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50