排队

Description

n个人排成一条直线（一排），给出队伍中每个人的身高，每个人只能看到站在他右边且个头比他小没有被其他人挡住（跟他身高相同也会挡出他）的人。请求出所有人可以看到的人数之和。
1<=N<=80,000

Sample Input

6
5
10
3
7
4
12
2

Sample Output

5

解题思路

这题就是单挑栈
所谓单调栈，也就是和单调队列差不多，也有单调递增和单调递减
单调递增栈：从栈顶到栈底的元素是严格递增
单调递减栈：从栈顶到栈底的元素是严格递减
但是单调栈只能从栈顶进出，不能从栈底进出
单调栈

AC代码

#include<iostream>
using namespace std;
long long n,o,s,a[80005],f[80005];
int main()
{
   
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];//输入
	f[++o]=n+1;//初值
	a[n+1]=2147483647;
	for(int i=n;i>=1;i--)
	{
   
		while(a[f[o]]<a[i]&&o>=1)o--;//如果当前数比后面的数要大，后面的数是没有贡献的，直接弹掉
		s+=f[o]-i-1;//此时栈顶的数是右边第一个大于等于a[i]的数，那么中间的数都比a[i]小，统计进答案
		f[++o]=i;//插入栈中
	}
	cout<<s;
}

谢谢