腾讯刷题 逛街

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

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

输入描述:

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

1<=n<=100000;

1<=wi<=100000;

输出描述:

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

输入例子1:

6

5 3 8 3 2 5

输出例子1:

3 3 5 4 4 4

例子说明1:

当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。

我首先想到的是暴力算法，因为看到数据量不是很大，两层循环，第一层循环下两个指针，从当前循环的元素开始，一个向前，一个向后，每个指针都伴随一个最大值，当节点大于最大值时，才进入视野并更新最大值，小于等于则省略，但是提交超时了。

第二次想到可用单调栈来实现，设置两个栈，一个储存向前遍历的节点，一个储存向后遍历的节点，不同于上述暴力算法，这次一个从头出发，一个从尾出发，例如，当结尾（理论上的结尾）的层数大于中间楼层的层数时，中间楼层是可以的看到的，所以，每次比较遍历到的元素和栈顶元素，若大于则更新，小于则进入。需要注意的是最后还要加上该楼层本身。

通过代码如下：

#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f
int main()
{
    int a[100001], b[100001];
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    stack<int>Front, After;
    for(int i=n;i>0;i--)
    {
        while(!After.empty() && a[i]>=After.top())
        {
            After.pop();
        }
        After.push(a[i]);
        b[i-1] = After.size();
    }
    cout<<b[1]+1<<" ";
    for(int i=1;i<=n;i++)
    {
        while(!Front.empty() && a[i]>=Front.top())
        {
            Front.pop();
        }
        Front.push(a[i]);
        b[i+1] += Front.size()+1;
    }
    for(int i=2;i<=n;i++)
    {
        printf("%d%c", b[i],(i==n)?'\n':' ');
    }
    return 0;
}

暴力超时代码如下：

#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
//6
//5 3 8 3 2 5
//3 3 5 4 4 4
using namespace std;
#define INF 0x3f3f3f3f
int main()
{
    int a[100001];
    int n, i;
    scanf("%d", &n);
    for(i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
    }
    int b[100001];
    for(i=1;i<=n;i++)
    {
        b[i] = 0;
    }
    int num_front, num_after;
    for(i=1;i<=n;i++)
    {
       int j = i - 1;
       if(j>0)
       {
           num_front = a[j];
           b[i]++;
           j--;
           while(j>0)
           {
               if(a[j] > num_front)
               {
                   b[i]++;
                   num_front = a[j];
                   j--;
               }
               else
               {
                   j--;
               }
           }
       }
       int k = i + 1;
       if(k<=n)
       {
           num_after = a[k];
           b[i]++;
           k++;
           while(k<=n)
           {

               if(a[k] > num_after)
               {
                   b[i]++;
                   num_after = a[k];
                   k++;
               }
               else
               {
                   k++;
               }
           }
       }
    }
    for(i=1;i<=n;i++)
    {
        printf("%d%c", b[i]+1, (i==n)?'\n':' ');
    }
    return 0;
}