LeetCode862 和至少为k的最短子数组

题目：

解析：
1、先构造前缀和数组
2、单调队列存放滑动窗口，目的求Sj-Si >=k的情况下，窗口最小。

代码：

class Solution {public int shortestSubarray(int[] nums, int k) {int n = nums.length;long[] sums = new long[n + 1];      // 注意这里加和后，容易超过int，加和用long数组for (int i = 1; i <= n; i++) {sums[i] = sums[i - 1] + nums[i - 1];}Deque<Integer> deque = new LinkedList<>();deque.add(0);int res = Integer.MAX_VALUE;for (int i = 1; i <= n; i++) {while (!deque.isEmpty() && sums[i] - sums[deque.peek()] >= k) { // 注意边界，求最小这里应该 >=res = Math.min(res, i - deque.poll());}//将所有大于等于s[i]的数删掉 问题：这里不删能怎么样，上面求最小值会守影响么？while (!deque.isEmpty() && sums[deque.peekLast()] >= sums[i]) {  // 注意边界，求最小这里应该 >=deque.pollLast();}deque.add(i);}if (res == Integer.MAX_VALUE) {return -1;}return res;}
}