【每日一题】单调队列、滑动窗口最大最小值

https://ac.nowcoder.com/acm/problem/50528
滑动窗口最大最小值

单调队列板子题

求最大值和求最小值分别维护一个单减和单增队列即可，队列内保存数组下标（方便判断是否在滑动窗口内），我这里使用deque使用

以求最大值为例：

队列的最前端是此次遍历的最大值的下标
当我们遇到新的数时，将新的数和双项队列的末尾比较，如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才停止
双项队列中的所有值都要在窗口范围内

#include 
using namespace std;
vector maxres;
vector minres;
void Window(vector nums, int k)
{
    deque dec;
    deque inc;
    for (int i = 0; i < k; ++i)
    {
        while (!dec.empty() && nums[i] > nums[dec.back()])
        {
            dec.pop_back();
        }
        while (!inc.empty() && nums[i] < nums[inc.back()])
        {
            inc.pop_back();
        }
        dec.push_back(i);
        inc.push_back(i);
    }
    maxres.push_back(nums[dec.front()]);
    minres.push_back(nums[inc.front()]);
    for (int i = k; i < nums.size(); ++i)
    {
        if (!dec.empty() && dec.front() <= i - k)
        {
            dec.pop_front();
        }
        if (!inc.empty() && inc.front() <= i - k)
        {
            inc.pop_front();
        }
        while (!dec.empty() && nums[i] > nums[dec.back()])
        {
            dec.pop_back();
        }
        while (!inc.empty() && nums[i] < nums[inc.back()])
        {
            inc.pop_back();
        }
        dec.push_back(i);
        inc.push_back(i);
        maxres.push_back(nums[dec.front()]);
        minres.push_back(nums[inc.front()]);
    }
    return;
}
void PPrint(){
    int len=minres.size();
    for(int i=0;i<len;++i){
        cout<<minres[i]<<" ";
    }
    cout << endl;
    len=maxres.size();
    for(int i=0;i<len;++i){
        cout<<maxres[i]<<" ";
    }
}
int main()
{
    int n, k;
    cin >> n >> k;
    vector nums(n, 0);
    for (int i = 0; i < n; ++i)
        cin >> nums[i];
    Window(nums,k);
    PPrint();
}