题目描述
小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。
小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）
Example1:
输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。
1<=n<=100000;
1<=wi<=100000;
输出描述:
输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。
输入
6
5 3 8 3 2 5
输出
3 3 5 4 4 4
说明
当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。
解题思路
- 单调栈使用
- 维护一个递减栈，如果height[i] > s.top(), (假设 现在栈元素为 8 3， 来了一个元素 4)，很明显要把3弹出去，下次累加 栈里的元素就是可以看到的个数。如果来个2，直接插入即可
- 然后从后往前再遍历一遍，思路是一样的，也要维持一个递减栈的形式，每次进行累加
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
int height[100001];
for(int i = 0; i < n; i++){
cin >> height[i];
}
stack<int> s1;
vector<int> res(n, 0);
for(int i = 0; i < n; i++){
res[i] += 1;
res[i] += s1.size();
while(!s1.empty() && s1.top() <= height[i]){ // 如果条件成立，即说明后面的高度要大，会挡住前面的楼
s1.pop();
}
s1.push(height[i]);
}
// s1.clear(); // stack 无clear操作
while(!s1.empty()){
s1.pop();
}
for(int i = n - 1; i >= 0; i--){
res[i] += s1.size();
while(!s1.empty() && s1.top() <= height[i]){
s1.pop();
}
s1.push(height[i]);
}
for(int i = 0; i < n; i++){
cout << res[i] << " ";
}
return 0;
}
