862. 和至少为 K 的最短子数组 (opens new window)

1.前缀和+单调队列

分析：用相邻前缀和之差来记录每个子数组之和，即便如此，前缀和暴力搜索的时间复杂度还是O(n平方)。因此使用单调队列来优化时间复杂度，这里单调的意思不仅队列保存的索引是递增的，同时索引对应的前缀和也是递增的。这里假设队首到队尾依次递减：

• 优化1：如果当前位置 i 与队尾元素 j 的前缀和之差大于等于k，那么队尾元素直接出队列。因为在 i 后面若存在m(m>i) 也满足与j的前缀和之差不小于k，得到的数组长度 m-j 肯定比 i-j 小。因此pre[j]只有第一次计算的结果可能是最小子数组，后面就没有用了。
• 优化2：如果当前位置 i 比队首位置 j 的前缀和大，那么队首元素直接出队列。因为如果在当前位置 i 之后存在m可以构成[j , m]的子数组，那么显然[i, m]也满足条件，并且子数组长度比前面队首元素构成的还要小。因此队列中比当前索引对应前缀和大的都需要移除队列。

这里单调队列保存是所有能够与当前位置 i (作为右边界)构成子数组的左边界索引。分析到这就很明了，滑动窗口或者双指针之所以做不了，是因为虽然左指针移动可以模拟上面的优化1，但是优化2仅使用两个指针做不到。

✨子数组和问题要想到转化为前缀和之差，并且创建时可以多开辟一个位置，将0作为哨兵节点，从而不需要单独考虑前缀和直接作为子数组和的情况。

✨无论是单调栈还是单调队列，核心原则都可以分为以下几个步：①将每个元素都入队/栈。②当前数据结构是否存在无用的/不会对最终结果产生印象/不会贡献其中一种可能答案的元素，那么就需要及时移除这些没有贡献的元素。

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        long[] pre=new long[nums.length+1];
        for(int i=0;i<nums.length;i++){
            //设置一个哨兵元素0：表示当前子树组取的前缀和
            pre[i+1]=pre[i]+nums[i];
        }
        int res=Integer.MAX_VALUE;
        Deque<Integer> queue=new LinkedList<>();
        queue.offerLast(0);
        for(int i=1;i<nums.length+1;i++){
            while(!queue.isEmpty()&&pre[i]-pre[queue.peekLast()]>=k){
                res=Math.min(res,i-queue.pollLast());
            }
            while(!queue.isEmpty()&&pre[queue.peekFirst()]>=pre[i]) queue.pollFirst();
            queue.offerFirst(i);
        }
        if(res==Integer.MAX_VALUE) return -1;
        return res;
    }
}