一道单调栈的题目

背景

今天偶然遇到一道单调栈的题目，顺便复习下闲置已久的算法知识，题目的意思大致就是给你一个区间，找到子段和>=K的一个最小子段。

思路

子段问题的关键是前缀和，先求一下

int sum[50005]={0};
for(int i=0;i<len;i++) sum[i+1] = sum[i] + A[i];

紧接着，关键就是维持一个单调栈，下面解释一下什么是单调栈，先给一段代码

deque<int> dq; //双端队列数据结构
for(int i=0;i<=len;i++){
   while(!dq.empty() && sum[i]<=sum[dq.back()]){ //当前前缀小于
         dq.pop_back();
   }
   dq.push_back(i);
}

举个例子 [1,3,-4,5,-7] 前缀和[1,4,0,5,-2]
单调栈遍历过程中变化(记录下标）
i=0: 0
i=1: 单调上升 push 1，deque中为0,1
i=2: 不单调了，重新来 pop掉0和1，push 2 即deque中的数为下标2
i=3: 单调，push 3，deque中为2，3
i=4:不单调，pop掉2，3，push进4，即deque中为4

基于单调栈，如何找到子段和>=K的一个最小子段呢，如下所示：

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int len = A.size();
        int sum[50005]={0};
        // sum[0]=A[0];
        for(int i=0;i<len;i++) sum[i+1] = sum[i] + A[i];
        deque<int> dq;
        int ans = len+1;
        for(int i=0;i<=len;i++){
            while(!dq.empty() && sum[i]<=sum[dq.back()]){ //维持单调
                dq.pop_back();
            }
            while(!dq.empty() && sum[i]>=sum[dq.front()] + K){ //判断满足条件的单调栈，找到最小的
                // int t = dq.front();
                ans = min(ans, i-dq.front());
                dq.pop_front();
            }
            dq.push_back(i);
        }
        return ans<len+1?ans:-1;
    }
};