单调队列的题目
滑动窗口
https://ac.nowcoder.com/acm/problem/50528
- 单调队列问题
a[l],a[l + 1],a[l + 2]....a[r-2],a[r-1],a[r],当这个区间往右移动的时候，只会a[l]离开窗口，a[r + 1]进入窗口，那么我们只需比较这个即可
典型单调队列题目，我们队列左端存的是当前最优解，当窗口往右移动时，我们看这个队列左端是不是已经不再 k 这个范围内了，如果是的话我们让他出队，然后我们看 a[i] 也就是当前新加的元素 ，如果他比队列中的某些元素小的话，那么他就可能成为后面的最优解，那么我们往前找到一个合适的位置来存储他，也就是他前面的元素都比他小，后面的元素都比他大。 - 注意队列中存的是他的下标 l = r = 1 开始 ,让第一个元素先进队 注意是 ++ r
#include<bits/stdc++.h> #define pr printf #define sc scanf #define fur(i,a,b) for(int i = a; i<= b ;i++) #define fdr(i,a,b) for(int i = a; i>= b ;i--) using namespace std; const int N = 1e6 + 5; int du[N],n ,k ,a[N]; typedef long long ll; int main() { // freopen("in.txt","r",stdin); sc("%d %d",&n ,&k); int l = 1 ,r = 1; for(int i = 1 ; i <= n ; i ++){ sc("%d",&a[i]); } du[l] = 1; if(k ==1)pr("%d ",a[1]); for(int i = 2 ; i <= n ;i ++){ if(i - du[l] >= k && l <= r)l++; while(l <= r && a[du[r ]] >=a[i]) r--; du[++r] = i; // ++ r 是因为他要在队尾插入 if(i>=k)pr("%d ",a[du[l]]); } puts(""); l = 1, r= 1; du[l] = 1; if(k ==1)pr("%d ",a[1]); for(int i = 2 ; i <= n ;i ++){ if(i - du[l] >= k && l <= r)l++; while(l <= r && a[du[r ]] <=a[i]) r--; du[++r] = i; if(i>=k)pr("%d ",a[du[l]]); } puts(""); return 0; }
网易公司福利 153人发布