奶牛排队
#include<iostream>
using namespace std;
const int N=1e6+10;
int stk[N],tt=0;
int n;
int main(){
scanf("%d",&n);
while(n--){
int x;
scanf("%d",&x);
while(tt&&stk[tt]>=x) tt--;
if(tt) printf("%d ",stk[tt]);
else printf("0 ");
stk[++tt]=x;
}
return 0;
}
相似数
#include<iostream>
using namespace std;
const int N=1e6+10;
int stk[N],tt=0;
int n;
int main(){
scanf("%d",&n);
while(n--){
int x;
scanf("%d",&x);
while(tt&&stk[tt]>=x) tt--;
if(tt) printf("%d ",stk[tt]);
else printf("0 ");
stk[++tt]=x;
}
return 0;
}
人数清点
https://oj.czos.cn/p/2032
两种方法,都是构造单调递减栈。
算法一
维护一个单调递减栈,栈储存下标(位置)。主要思想:求每一个人能看到的人的数量。具体思路:按窗口第一位同学开始到最后一位同学的顺序,求每个同学前面离他最近的身高>=他的同学的位置,如果栈为空,说明他前面的身高比他都低,那么他能看到的人数就是(i-1)(本题下标从1开始),如果栈不为空,那么他能看到的人数就是(i-stk[tt]-1),求和即可。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=80010;
typedef long long LL;
//栈从1开始存,存的是下标
int stk[N],tt=0;
int n,a[N];
int main(){
scanf("%d",&n);
//由于栈从1开始,那么也从1开始存数据,与数据结构保持一致
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
//由于数据是从最后一名同学输入的,所以需要翻转一下
reverse(a+1,a+n+1);
//答案数量会爆int,用long long
LL res=0;
//本质是在找数组中每个数左边第一个大于等于他的数的下标
for(int i=1;i<=n;i++){
while(tt&&a[stk[tt]]<a[i]) tt--;
if(tt) res+=(i-stk[tt]-1);
else res+=(i-1);
stk[++tt]=i;
}
printf("%lld",res);
return 0;
}
算法二
同样是维护一个单调递减栈。 主要思想:求每个人能被多少个人看到。 具体思路:按题目输入的顺序处理(从队尾到队首),求每个人左边(相当于后边)最近的大于他的身高的问题,栈中的元素个数就是这个同学能被多少人看到,求和即可。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=80010;
typedef long long LL;
int stk[N],tt=0;
int n;
int main(){
scanf("%d",&n);
LL res=0;
while(n--){
int x;
scanf("%d",&x);
while(tt&&stk[tt]<=x) tt--;
res+=tt;
stk[++tt]=x;
}
printf("%lld",res);
return 0;
}
牛的视野
与人数清点一模一样,除了数据范围不同。