Daily LeetCode – day0089 0862. Shortest Subarray with Sum at Least K

import java.util.ArrayDeque;
import java.util.Deque;

// 0862. Shortest Subarray with Sum at Least K
class Solution {
    public int shortestSubarray(int[] nums, int K) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        Deque<Integer> deque = new ArrayDeque<>();
        int ans = n + 1;
        for (int i = 0; i < n + 1; ++i) {
            while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= K) {
                ans = Math.min(ans, i - deque.pollFirst());
            }
            while (!deque.isEmpty() && prefix[i] <= prefix[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        return ans <= n ? ans : -1;
    }
}

学习笔记：
这是一道困难题。需要用到前缀和和单调队列的思想。
需要连续的一串数字也就是子数组的和大于k，那么就相当于两个前缀和的差大于k。
把所有单调递增（相等也行）的前缀和放入队列，
然后难点是再走一圈判断互相之间有没有得到最小长度。
那我们可以保证队尾和队首之间的差，一旦大于等于k了，就判断是否是最短，判断完把队首也弹出了。