forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode03_GasStation.java
More file actions
53 lines (48 loc) · 1.18 KB
/
Code03_GasStation.java
File metadata and controls
53 lines (48 loc) · 1.18 KB
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
package class24;
import java.util.LinkedList;
// 测试链接：https://leetcode.com/problems/gas-station
public class Code03_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;
}
}