滑动窗口-窗口中的最大/小值-单调队列

求窗口的最大值 

#include <iostream>

//滑动窗口最大值用单调队列q[]，q存储候选最大值的下标

//队列头是最大值的下标

using namespace std;

const int N=100010;

int nums[N],q[N];

int hh=0,tt=-1;// hh 是队头指针，tt 是队尾指针，初始为空队列

int main(){

    int n,k;

    cin>>n>>k;

    for(int i=0;i<n;i++){

    cin>>nums[i];

   

    if(hh<=tt&&q[hh]<i-k+1) hh++;

//先判断不是空队列，如果队列头在滑动窗口左侧，hh往右移动

    while(hh<=tt&&nums[q[tt]] < nums[i]) tt--;

    //判断队列尾部的数值，如果新加入的都大于队尾数值，那么去掉队尾

    //新来的数会“打掉”比它小的所有队尾

    q[++tt]=i;//把当前下标i加入队尾

    if(i>=k-1) cout<<nums[q[hh]]<<' ';//i必须滑动完第一个窗口，开始输出nums[q[hh]]

}  return 0;

}

滑动窗口最小值

队列头部是最小的，递增

 只改一个地方

while (hh <= tt && nums[q[tt]] > nums[i]) tt--;

nums[i] 都小于队列尾的数字，赶紧去掉tt

如果队尾比当前值大，不对了！弹出去