题目分析

这个题目有点难度，如果题目中元素的数据范围均为正数，则可以使用滑动窗口来求解，但是本题有负数，因此sliding window是不合适的。那应该怎么求解呢？

单调双端队列

本题的题解可以参考灵茶山艾府(灵神)的思路，因为子数组是连续的，我们想要求解某一段的区间和，可以使用前缀和优化，因此先求出前缀和cursum[i]，表示前i个元素之和，cursum[0] = 0。

从左到右遍历，思考两种特殊情况，假设当前已经遍历到第j个元素

设i为左端点，如果cursum[j] - cursum[i] >= k，说明从i + 1元素开始到j的元素之和大于等于k，因此从i开始的最短长度为k，后面的情况和i已经无关了，因此可以将左端点i移除。
设i为右端点，如果cursum[j] <= cursum[i]，且后面某个位置x满足cursum[x] - cursum[i] >= k，那么一定有cursum[x] - cursum[j] >= k，且j在i的后面，所以从j + 1元素到x元素是更优的选择，和i也已经无关了，可以将右端点i移除。

由2可知，这个遍历会维护一个单调递增的栈，又因为1会从左边移除，因为要维护一个单调递增的双端队列。

算法的**时间复杂度为O(n)，空间复杂度为O(n)**。

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] curSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            curSum[i + 1] = curSum[i] + nums[i];
        }
        int res = n + 1;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i <= n; i++) {
            while (!deque.isEmpty() && curSum[i] - curSum[deque.getFirst()] >= k) {
                res = Math.min(res, i - deque.removeFirst());
            }
            while (!deque.isEmpty() && curSum[i] <= curSum[deque.getLast()]) {
                deque.removeLast();
            }
            deque.add(i);
        }
        return res == n + 1 ? -1 : res;
    }
}

刷题总结

单调栈和单调队列的题目往往都比较困难，希望小伙伴们能多做一些相关的题目。