Sliding Window(单调队列)
Sliding Window
https://ac.nowcoder.com/acm/problem/51001
存一下单调队列板子
题意
一个长度为n的序列,求每k个连续的元素的最大值和最小值。
解题思路
用两遍单调队列分别维护最大值和最小值。
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; int a[1000010],que[1000010]; //单调队列中存数组下标 int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,k; cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; int l=1,r=1; que[r++]=1; if(k==1) cout<<a[1]<<" "; //维护最小值 for(int i=2;i<=n;i++){ //若队列非空,且队首已不再窗口内,队首出队 if(l<r&&i-que[l]>=k) l++; //若队列非空,且队尾所指元素大于当前元素,由于要维护最小值,队尾出队 while(l<r&&a[i]<a[que[r-1]]) r--; que[r++]=i; if(i>=k) cout<<a[que[l]]<<" "; } cout<<endl; //维护最大值 l=r=1; que[r++]=1; if(k==1) cout<<a[1]<<" "; for(int i=2;i<=n;i++){ //若队列非空,且队首已不再窗口内,队首出队 if(l<r&&i-que[l]>=k) l++; //若队列非空,且队尾所指元素小于当前元素,由于要维护最大值,队尾出队 while(l<r&&a[i]>a[que[r-1]]) r--; que[r++]=i; if(i>=k) cout<<a[que[l]]<<" "; } cout<<endl; return 0; }