题解 | #Sliding Window#

/*
1. 需要维护：尾部插入，删除，头部删除，查找-->所以用deque
2. deque队列维护的是下标值，不是值

*/
#include<bits/stdc++.h>
using namespace std;

int n,k;
int a[1000010];
deque<int> dq;

int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        while(!dq.empty() && a[dq.back()] > a[i])
            dq.pop_back();
        if(!dq.empty() && i-dq.front()>=k)
            dq.pop_front();
        dq.push_back(i);
        if(i>=k-1)
            cout<<a[dq.front()]<<" ";
    }
    cout<<endl;
    dq.clear();
    for(int i=0;i<n;i++)
    {
        //dq.push_back(i);不可以放前面，否则a[dq.back()] < a[i]就是执行的a[i]< a[i]
        while(!dq.empty() && a[dq.back()] < a[i])
            dq.pop_back();
        if(!dq.empty() && i-dq.front()>=k)
            dq.pop_front();
        dq.push_back(i);
        if(i>=k-1)
            cout<<a[dq.front()]<<" ";
    }
    //错误：不可以存值，存下标不会出错
    /*
    输入：
    8 3
    8 7 6 7 7 6 5 4
    输出：
    6 6 6 6 5 4 
    8 8 7 7 7 6 
    */
//     for(int i=0;i<n;i++)
//     {
//         while(!dq.empty() && dq.back() < a[i])
//             dq.pop_back();
//         if(!dq.empty() && dq.size()>=k)
//             dq.pop_front();
//         dq.push_back(a[i]);
//         if(i>=k-1)
//             cout<<dq.front()<<" ";
//     }
    return 0;
}