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

用之前的保留标记map只能过百分之八十的用例，原因是最坏时间是平房复杂度；

所以只能通过单调栈来进行；

这里比较难理解，没看到几个说人话的；

当一段序列无负数，可知序列必定为单调递增；

例如前缀和：
1，2，4，5，如果k=1；
最先满足条件的是2-1；

观察一下4，4虽然也满足4-1=3>1，但是序列过长；

换句话说，由于他之前的2已经满足，他就没有探寻2以前序列的必要了，就算满足也会比2满足的情况长；

所以对于单调队列，维护递增，每次从队头开始对比，如果满足就踢出去，直到不满足就可以；

如果一段序列为负数，可知道必定会出现前缀和下降情况，并不能保证前缀和全部为递增；

例如：
1，2，4，2，5，如果k=3；
则有两段序列满足：[1，2，4]以及[2，5]；

可以看到当遍历到第二个2的时候，会发生前缀和序列递减；

此时应该从后向前弹出所有大于该2的值；

原因有以下两点：

1. 弹出是因为保证递增性，减去比2大的和减去2，肯定减去2的优先满足条件；
2. 弹出也是为了满足去见最小，因为如果离后续判断元素近的2都能满足，还要比2大还离判断元素远的干什么？

class Solution {
public:
    int shortestSubarray(vector& nums, int k) {
        int n=nums.size();
        vectordp(n+1,0);
        int maxn=INT_MAX;
        mapmp;
        mp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=dp[i-1]+nums[i-1];
            int search=dp[i]-k;
            for(auto it=mp.begin();it!=mp.end();it++){
                if(it->first>search)
                    break;
                maxn=min(maxn,i-it->second);
            }
            mp[dp[i]]=i;
        }
        if(maxn==INT_MAX)
            return -1;
        return maxn;
    }
};```