单调栈的完美应用场景. 结合单调栈和prefix sum. 这两个都是很好的解题方法.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int shortestSubarray(int[] nums, int k) {
long[] sumArray = new long[nums.length];
long sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
sumArray[i] = sum;
}
Deque<Integer> monoq = new LinkedList<>();
int ans = nums.length + 1;
for (int i = 0; i < sumArray.length; i++) {
while (!monoq.isEmpty() && sumArray[monoq.peekLast()] >= sumArray[i]) {
monoq.pollLast();
}
while (!monoq.isEmpty() && sumArray[i] - sumArray[monoq.peekFirst()] >= k) {
ans = Math.min(ans, i - monoq.pollFirst());
}
ans = sumArray[i] >= k ? Math.min(ans, i + 1) : ans;
monoq.offer(i);
}
return ans == nums.length + 1 ? -1 : ans;
}
}
|
这道题经典啊. 单调queue的完美应用. 首先要注意的是我们prefix sum要用long数组存, 因为可能会overflow. 其次18行要注意, 因为可能某个位置的prefix sum不需要减前面的某个prefix sum, 只有这样才能凑成至少为k, 也就是15行的循环不会进去, 于是有了18行, 这一行就是为了捕捉这种情况.
时间复杂度: O(n) two pass
空间复杂度: O(n) 用了prefix sum array和deque.
