862. Shortest Subarray with Sum at Least K

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int minLength = Integer.MAX_VALUE;

        // 注意题目数组所有元素和可能大于 Integer.MAX_VALUE, 所以此处使用 long 数组
        long[] prefixSumArray = new long[nums.length + 1]; // 前 i 个元素的前缀和，前缀和之差即为连续子数组和，因为元素可能为负数，所以前缀和并不一定单调递增
        for (int i = 1; i < prefixSumArray.length; i++) {
            prefixSumArray[i] = prefixSumArray[i - 1] + nums[i - 1];
        }

        Deque<Integer> increaseDeque = new LinkedList<>(); // 严格单调递增的前缀和对应的索引
        for (int i = 0; i < prefixSumArray.length; i++) {
            long prefixSum = prefixSumArray[i];

            // 注意是将 prefixSum 与前缀和数组中的元素进行比较
            while (!increaseDeque.isEmpty() && prefixSum - prefixSumArray[increaseDeque.getFirst()] >= k) {
                minLength = Math.min(minLength, i - increaseDeque.pollFirst());
            }
            while (!increaseDeque.isEmpty() && prefixSum <= prefixSumArray[increaseDeque.getLast()]) {
                // 当 prefixSum 小于等于单调队列中的最大值时，说明差值可能越大，子数组长度就可能越小
                increaseDeque.pollLast();
            }

            increaseDeque.addLast(i);
        }

        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}

注意该题数组元素可能含有负数，所以不能使用常规的滑动窗口解题，如：[84, -37, 32, 40, 95]，k = 167，若使用常规的滑动窗口则无法将 -37 移除窗口。

References

862. Shortest Subarray with Sum at Least K