单调栈(该点左边第一个小于它的值)
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl '\n' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int s[maxn],tt; int main(){ int n;cin>>n; rep(i,1,n){ int x;cin>>x; while(tt&&s[tt]>=x) tt--; if(tt) cout<<s[tt]<<" "; else cout<<"-1 "; s[++tt]=x; } }单调队列(求k个窗口中最大最小值)
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl '\n' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e6+5; int a[maxn],q[maxn],p[maxn]; int main(){ int n,k;scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int head=1,tail=0; for(int i=1;i<=n;i++){ while(head<=tail&&q[tail]>=a[i]) --tail; q[++tail]=a[i]; p[tail]=i; while(p[head]<=i-k) head++; if(i>=k) printf("%d ",q[head]); } puts(""); head=1,tail=0; for(int i=1;i<=n;i++){ while(head<=tail&&q[tail]<=a[i]) --tail; q[++tail]=a[i]; p[tail]=i; while(p[head]<=i-k) head++; if(i>=k) printf("%d ",q[head]); } }