单调栈及单调队列
单调栈
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9;
const ll NUM =1e5+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x);}
int a[NUM],st[NUM],l[NUM],r[NUM];
int main(){
int n;
while(cin>>n){
if(n==0) break;
for(int i=1;i<=n;i++) a[i]=read();
int top=0;
st[0]=0;//第一个元素的左边第一个比它小的下标是0
for(int i=1;i<=n;i++){
while(top&&a[st[top]]>=a[i]) top--;
l[i]=st[top];
st[++top]=i;
}
top=0;
st[0]=n+1;//最后一个元素右边第一个比它小的元素下标是n+1
for(int i=n;i>=1;i--){
while(top&&a[st[top]]>=a[i]) top--;
r[i]=st[top];
st[++top]=i;
}
ll ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,1ll*(r[i]-l[i]-1)*a[i]);
}
cout<<ans<<endl;
}
} 5 2 4 3 1
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7, mod = 1e9 + 7;
typedef long long ll;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int n, a[maxn], st[maxn], top, l[maxn], r[maxn];
int main() {
int t = read();
int Case = 1;
while (t--) {
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
top = 0;
st[0] = 0;
for (int i = 1; i <= n; i++) {
int maxx = -1, k = 0;
while (top && a[st[top]] < a[i]) {
if(maxx < a[st[top]]) {
maxx = a[st[top]];
k = st[top];
}
top--;
}
l[i] = k;
st[++top] = i;
}
top = 0;
for (int i = n; i >= 1; i--) {
int maxx = -1, k = 0;
while (top && a[st[top]] < a[i]) {
if(maxx < a[st[top]]) {
maxx = a[st[top]];
k = st[top];
}
top--;
}
r[i] = k;
st[++top] = i;
}
printf("Case %d:\n", Case++);
for (int i = 1; i <= n; i++)
printf("%d %d\n", l[i], r[i]);
}
return 0;
} //10 9 8 2 3 6 5 7
单调队列
poj2823
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e6 + 7, mod = 1e9 + 7;
typedef long long ll;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int n, k, a[maxn];
int head, tail, que[maxn];
int maxx[maxn], minx[maxn];
int main() {
n = read(); k = read();
for (int i = 1; i <= n; i++) a[i] = read();
head = 1, tail = 0;
for (int i = 1; i <= n; i++) {
while (head <= tail && a[que[tail]] > a[i]) tail--;
que[++tail] = i;
while (head <= tail && que[head] <= i - k) head++;
if(i >= k) minx[i] = a[que[head]];
}
head = 1, tail = 0;
for (int i = 1; i <= n; i++) {
while (head <= tail && a[que[tail]] < a[i]) tail--;
que[++tail] = i;
while (head <= tail && que[head] <= i - k) head++;
if(i >= k) maxx[i] = a[que[head]];
}
for (int i = k; i <= n; i++)
printf("%d ", minx[i]);
printf("\n");
for (int i = k; i <= n; i++)
printf("%d ", maxx[i]);
printf("\n");
return 0;
}