小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。

小Q从第一栋一直走到了最后一栋，小Q从来没有看到过这么多高楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

输入描述：

输入第一行将包含一个数字n,表示楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表一栋楼的高度。

1<=n<=100000;

1<=wi<=100000;

输出描述：

输出一行，包含空格分隔的m个数字vi,分别代表小Q在第i栋楼的时候能看到的楼的数量。

 

这道题，如果用最常规的办法，一定是超时的，因为复杂度是O(n^2)，这明显不是一个很好的解法。那么怎么用O(nlogn)的时间复杂度呢？实际上单调栈就可以很好的解决这个问题。首先求出来从一个点向左看增的单调栈（也就是从左往右减的单调栈，表示小Q往左看能看到的楼的数量），然后求出来一个点向右看增的单调栈，最后对应位置相加再加1就可以得到总的结果了。

 

代码如下：

int main(){//实现一个单调栈int n;cin >> n;int front[100005];int back[100005];int height[100005];//表示每个楼的高度stack<int> st_left2right;//表示楼的高度的单调栈for (int i = 0; i < n; i++){cin >> height[i];front[i] = st_left2right.size();//对单调栈进行处理，实现一个高度下降的单调栈if (i == 0) st_left2right.push(height[0]);//第一个需要特殊处理else if (st_left2right.top() > height[i]) st_left2right.push(height[i]);else{while (!st_left2right.empty() && st_left2right.top() <= height[i]){st_left2right.pop();}st_left2right.push(height[i]);}}stack <int> st_right2left;for (int i = n - 1; i >= 0; i--){back[i] = st_right2left.size();if (i == n - 1) st_right2left.push(height[i]);else if (st_right2left.top() > height[i]) st_right2left.push(height[i]);else{while (!st_right2left.empty() && st_right2left.top() <= height[i]){st_right2left.pop();}st_right2left.push(height[i]);}}for (int i = 0; i < n; i++){cout << front[i] + back[i] + 1<<" ";}cout << endl;system("pause");return 0;}

我自己菜，就要多练习，多思考。