【数据结构】【单调栈】视野总和

题目描述

有n个人站成一排，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发型人数的总和是多少。

输入

第一行输入n的值 0<n<=106

第二行输入n个数，每个数都小于1000005正整数空格隔开

输出

所有人能看到其他人发型总和。

样例输入

8
1 10 5 6 9 4 3 10

样例输出

8

#include<bits/stdc++.h>
#define started() cin.tie(0),cout.tie(0)
using namespace std;
vector<long long> wt;
long long n,a,sum;
long long inc(vector<long long> vt){vt.push_back(INT_MAX);stack<int> st;for(int i=0;i<vt.size();i++){if(st.empty()||vt[st.top()]>vt[i]){st.push(i);}else{while(!st.empty()&&vt[st.top()]<=vt[i]){int tops=st.top();st.pop();sum+=(i-tops-1);}st.push(i);}}return sum;
}int main(){started();cin>>n;for(int i=1;i<=n;i++){cin>>a;wt.push_back(a);}cout<<inc(wt);
}