poj2823_滑动窗口(单调队列)

单调队列

滑动窗口

• 如果没有窗口的限制，而求[0,i]的最值，模拟单调栈（一头不变）解决，求最大值就维护一个单调递减的,输出栈的底部(模拟的栈),求最小值同理
• 当窗口限制的时候，我开始想的是队列存值 (用单调队列来维护窗口内的值)，如果仅仅存的是值，那么将无法知道队列中值是否在窗口内，
• 此时如果队列存的是 该值的下标那么将很好解决窗口的范围问题，

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
const int maxn=1e6+10;
int num[maxn];
deque<int> quemax,quemin;
vector<int> num_max,num_min;
int n,k;
int main() {
//    freopen("a.txt","r",stdin);
    scanf("%d%d",&n,&k);
    for (int i=0;i<n;i++) scanf("%d",&num[i]);
    
    //求最大值 队列保持单点递减，控制范围,
    for (int i=0;i<n;i++) {
        while ( !quemax.empty() && num[i]>num[quemax.back()] ) quemax.pop_back();//保持单调递减
        quemax.push_back(i);//存该值下标
        // 3-3 =0 [1,3]，将队列头部值不在窗口内的清除
        while ( i-k>=quemax.front() ) quemax.pop_front();
        if( i>=k-1 ) {
            num_max.push_back( num[quemax.front()] );
        }
    }
    //同理，求窗口最小值，队列保持单调递增，
    for (int i=0;i<n;i++) {
        while ( !quemin.empty() && num[i]<num[quemin.back()] ) quemin.pop_back();
        quemin.push_back(i);
        while ( i-k>=quemin.front() ) quemin.pop_front();
        if( i>=k-1 ) num_min.push_back( num[quemin.front()] );
    }
    for (int i=0;i<num_min.size(); i++) printf("%d ",num_min[i]);
    printf("\n");
    for (int i=0;i<num_max.size(); i++) printf("%d ",num_max[i]);

    return 0;
}