LeetCode 134. Gas Station
題目描述
思路
暴力解法 O(N^2)
我們可以通過生成輔助數組來驗證良好出發點
int[]h
這個數組的長度和cost數組長度一致,且這個數組的每個元素的生成邏輯是:
h[i]=gas[i]-cost[i];
h(i) 往後累加,並回到i位置,不出現負數,就是良好出發點 ,這個i位置就是良好出發點
// 暴力解法 O(N^2)
public static int canCompleteCircuit3(int[] gas, int[] cost) {
int n = gas.length;
int[] h = new int[n];
for (int i = 0; i < n; i++) {
h[i] = gas[i] - cost[i];
}
// 標記良好出發點的位置,開始是-1,說明沒有找到良好出發點
int good = -1;
// h[i] 一直往後累加,累加和記錄在preSum中,回到本身,如果不出現負數,i位置就是良好出發點
int preSum;
for (int i = 0; i < n; i++) {
preSum = h[i];
for (int j = i + 1; j < n + i + 1; j++) {
if (preSum < 0) {
break;
}
// int index = j % n
int index = j > n - 1 ? j - n : j;
preSum += h[index];
}
if (preSum >= 0) {
good = i;
}
}
return good;
}
滑動窗口 時間複雜度 O(N) 空間複雜度 O(N)
首先,我們還是需要生成h[i]數組
h[i]=gas[i]-cost[i];
假設生成的h[i]數組如下:
[1,-1,0,3,-1]
我們生成其累加和數組preSum[i]
[1,0,0,3,2]
用這個累加和數組在和h[i]數組相加,得到一個兩倍長度的數組
[1,0,0,3,2,3,2,2,5,4]
求針對這個數組,滑動窗口為n(n為原數組長度)的最小值,如果第i個窗口內的最小值減去窗口前一個位置的值,如果小於0,則i號位置不是良好出發點
比如
L…L + n – 1 是第x個窗口,最小值m,
如果 m – num[L-1] >= 0 則x是良好出發點
反之,則x不是良好出發點, 完整程式碼:
public static int canCompleteCircuit(int[] gas, int[] cost) {
int len = gas.length;
int doubleLen = len << 1;
int[] h = new int[doubleLen];
h[0] = gas[0] - cost[0];
for (int i = 1; i < doubleLen; i++) {
if (i < len) {
h[i] = gas[i] - cost[i];
h[i] += h[i - 1];
}
if (i >= len) {
h[i] = h[len - 1] + h[i - len];
}
}
LinkedList<Integer> qMin = new LinkedList<>();
int r = 0;
int index = 0;
while (r < doubleLen) {
while (!qMin.isEmpty() && h[qMin.peekLast()] >= h[r]) {
qMin.pollLast();
}
qMin.addLast(r);
if (qMin.peekFirst() == r - len) {
qMin.pollFirst();
}
if (r >= len - 1) {
if (r == len - 1) {
if (h[qMin.peekFirst()] >= 0) {
return index;
}
} else {
if (h[qMin.peekFirst()] - h[r - len] >= 0) {
return index;
}
}
index++;
}
r++;
}
return -1;
}
時間複雜度 O(N) 空間複雜度 O(1) 的解法
TODO