《有意思的题》和至少为 K 的最短子数组

问题：

力扣的第209道题209. 长度最小的子数组 - 力扣（LeetCode）很简单的滑动窗口，但是如果数组中有负数，那就有点麻烦了，例如力扣的第86道题862. 和至少为 K 的最短子数组 - 力扣（LeetCode）

解题思路：

前缀和加双端队列（保持单调递增）

遍历前缀

如果队尾的元素大于等于前缀i，表明，此时新添的元素是个负数，对于后续找找满足的条件可以去除更多的个数，所以维护队列的单调

如果当前前缀i-队列的首位>=k,记录此时的长度，然后poll首列，因为后续满足的条件都没有当前短

代码：

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int size = nums.length;
        long[] pre = new long[size + 1];
        int res = size + 1;
        for(int i = 1; i <= size; i++){
            pre[i] = pre[i - 1] + nums[i - 1];
            if(nums[i - 1] == k){
                return 1;
            }
        } 

        Deque<Integer> dq = new LinkedList<>();
        for(int i = 0; i <= size; i++){
            while(!dq.isEmpty() && pre[i] <= pre[dq.getLast()]){
                dq.removeLast();
            }
            while(!dq.isEmpty() && pre[i] - pre[dq.peek()]>=k){
                res = Math.min(res,i - dq.poll());
            }
            dq.add(i);
        }
        return res == size + 1? -1 : res;
    }
}