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

一个双端单调队列：如果新加入的数比队列尾的数小，那么队列尾的数就可以丢去，这是因为如果未来的一个数能和队列尾的数满足条件，那么也一定可以和新加入的数满足条件。 另外，如果一个数和队列头的数已经满足了条件，那么队列头的数就不用保留了，这是因为以后加入的数，就算能和队列头的数满足条件，也会比现在的长度大。

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n=nums.size();
        int res=n+1;
        deque<int> q;
        q.push_back(0);
        long long p[n+1];
        for(int i=1;i<=nums.size();i++){
            p[i]=p[i-1]+nums[i-1];
        }
        for(int i=1;i<=nums.size();i++){
            while(!q.empty()&&p[i]<=p[q.back()]){
                q.pop_back();
            }
            while(!q.empty()&&p[i]-p[q.front()]>=k){
                res=min(res,i-q.front());
                q.pop_front();
            }
            q.push_back(i);
        }
        return res==n+1?-1:res;
    }
};