862.和至少为 K 的最短子数组

862. 和至少为 K 的最短子数组

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

示例 1：

输入：nums = [1], k = 1
输出：1

示例 2：

输入：nums = [1,2], k = 4
输出：-1

示例 3：

输入：nums = [2,-1,2], k = 3
输出：3

提示：

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109

C++

/*
添加负数之后窗口的滑动就没有单向性了，因此无法使用滑动窗口解决
正确的做法是维护一个单增的单调队列(可以是数组)存前缀和，如果队尾减队首大于等于k，那么队首就找到了以他开始的最短的子数组，队首就可以退位了

我们需要维护一个严格单调递增的队列  q，队列中存储的是前缀和数组 s[i] 的下标。注意，这里的单调递增是指下标对应的前缀和的大小，而不是下标的大小。
*/

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n + 1);
        for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + nums[i - 1];
        deque<int> q; // q队头 -> 队尾   s[]小 -> 大
        int res = n + 1;
        
        // [84,-37,32,40,95]  167   s = [0, 84, 47, 79, 119, 214]
        // 第0轮, q =[0]
        // 第1轮, q =[0, 84]
        // 第2轮, q =[0, 47]
        // 第3轮, q =[0, 47, 79]
        // 第4轮, q =[0, 47, 79, 119]
        // 第5轮, q =[0, 47, 79, 119, 214]
        for (int i = 0; i <= n; i++) {
            while (!q.empty() && s[i] - s[q.front()] >= k) { 
                res = min(res, i - q.front());
                q.pop_front();
            }
            while (!q.empty() && s[q.back()] >= s[i]) q.pop_back();
            q.push_back(i);
        }
        return res > n ? -1 : res;
    }
};