Copy
#include<cstdio>
#define reg register
const int MAX=7000001;
int n,k,a[MAX];
int Min[MAX],Max[MAX];
struct node{
int x,id; //x:值 id:位置（原序列中的下标）
}v[MAX];
void get_min(){
int head=1,tail=0; //默认起始位置为1 因为插入是v[++tail]故初始化为0
for(reg int i=0;i<k-1;++i){ //根据题目 前m-1个先直接进入队列
while(head<=tail && v[tail].x>=a[i]) --tail;
v[++tail].x=a[i], v[tail].id=i;
}
for(reg int i=k-1;i<n;++i){
while(head<=tail && v[tail].x>=a[i]) --tail;
v[++tail].x=a[i], v[tail].id=i;
while(v[head].id<i-k+1) ++head;
Min[i-k+1]=v[head].x;
//道理同上，当然了，要把已经超出范围的从head开始排出
//然后每个队首则是目前k个数的最小值
}
}
void get_max(){ //最大值同最小值的道理，只不过是维护的是递减队列
int head=1,tail=0;
for(reg int i=0;i<k-1;++i){
while(head<=tail && v[tail].x<=a[i]) --tail;
v[++tail].x=a[i], v[tail].id=i;
}
for(reg int i=k-1;i<n;++i){
while(head<=tail && v[tail].x<=a[i]) --tail;
v[++tail].x=a[i], v[tail].id=i;
while(v[head].id<i-k+1) ++head;
Max[i-k+1]=v[head].x;
}
}
void output(){
printf("%d",Min[0]);
for(reg int i=1;i<n-k+1;++i) printf(" %d",Min[i]);
printf("\n%d",Max[0]);
for(reg int i=1;i<n-k+1;++i) printf(" %d",Max[i]);
printf("\n");
}
int main(){
scanf("%d%d",&n,&k);
for(reg int i=0;i<n;++i) scanf("%d",&a[i]);
get_min(); get_max(); output();
return 0;
}
关于单调栈的一道题目
问题描述
地上从左到右竖立着 n 块木板，从 1 到 n 依次编号，如下图所示。我们知道每块木板的高度，在第 n 块木板右侧竖立着一块高度无限大的木板，现对每块木板依次做如下的操作：对于第 i 块木板，我们从其右侧开始倒水，直到水的高度等于第 i 块木板的高度，倒入的水会淹没 ai 块木板（如果木板左右两侧水的高度大于等于木板高度即视为木板被淹没），求 n 次操作后，所有 ai 的和是多少。如图上所示，在第 4 块木板右侧倒水，可以淹没第 5 块和第 6 块一共 2 块木板，a4 = 2。
解法①
暴力求解，复杂度是O(n2)
例如现在存在5块木板
每块木板从左至右高分别为
10，5，8，12，6
从第一块木板（高度为10）右侧开始倒水，当水到达第四块木板（高度为12）时，可以淹没第一块木板
即第一块木板至第四块木板之间的木板数量，即4-1-1 = 2，a1 = 2；
也就是说：寻找在第 i 个木板右边第一个比它大的木板j，ai 就等于木板 i 和木板 j 之间的木板数
同理得到
a2=0
a3=0
a4=1
a5=0
sum = a1 + a2 +a3 +a4 +a5 = 3
于是，问题就变成了寻找在第 i 个数右边第一个比它大的数。可以暴力求解，从 1 循环到 n，对每块木板再往右循环一遍，这样的时间复杂度是O(n2) 。