本题的链接是：逛街

题目描述

小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栋楼。

解题思路1-暴力法

一开始用到的方法是简单粗暴的暴力法，结果只有60%的测试用例通过，时间复杂度是 $O(n^2)$ ，明显不符合题意。

代码

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int nums[] = new int[count];
        int res[] = new int[count];

        int index = 0;
//        输入数据
        while(count-->0){
            nums[index++] = scanner.nextInt();
        }
        int start, end;
        for(int i=0;i<index;i++){
            int result = 0;
            int low = 0,up=0;
            start = i-1;
            end = i+1;
            if(start>=0){
                low = nums[start];
                result++;
            }
            start--;
            while(start>=0){
                if(nums[start]>low){
                    result++;
                    low = nums[start];

                }
                start--;
            }
            if(end<index){
                up = nums[end];
                result++;
            }
            end++;
            while(end<index){
                if(nums[end]>up){
                    result++;
                    up = nums[end];

                }
                end++;
            }
            res[i] = result+1;

        }
        for(int i=0;i<index;i++)
            System.out.print(res[i] + " ");
        System.out.println();
    }

思路分析:

可以用到单调栈，顾名思义就是栈里面的元素是单调递增的，这样的话只要判断元素是否大于栈里面的元素就可以进行判断有多少栋楼比当前的楼高。
例如：
5 3 8 3 2 5
我们用一个向前看的栈Stack进行说明，他是个单调栈，里面所有的元素都是递增的，用数组left表示向前看有多少楼可以看到，例如left[1]=1表示在位置1向左边看可以看到1栋楼。
遍历数组：
i=0: left[0] = 0 stack = [5]
i=1: left[1] = 1 stack = [5,3]
i=2: left[2] = 2 stack = 8
i=3: left[3] =1 stack = [8,3]
i=4: left[4] =2 stack = [8,3,2]
i=5:left[5] = 3 stack = [8,5]（5的右边还是可以看到8）

单调栈代码

    public static void main(String[] args) {
    // write your code here
//        用户输入数据
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int []arr = new int[n];
//        赋值
        for(int i=0;i<n;i++)
            arr[i] = scanner.nextInt();
//        给定2个堆栈：分别向左边右边看齐
        Stack<Integer> left_stack = new Stack<>();
        Stack<Integer> right_stack = new Stack<>();

//        向左看和向右看的楼的数量
        int []left_count = new int[n],right_count = new int[n];
        int j=0;
        for(int i=0;i<n;i++){
//            从右边到左边看
            j = n-i-1;
            left_count[i] = left_stack.size();
            right_count[j] = right_stack.size();
//            如果当前的数字比栈顶的数字还要大的话，就出栈，因为已经被挡住了
            while(!left_stack.isEmpty() && left_stack.peek() <= arr[i])
                left_stack.pop();
            while(!right_stack.isEmpty() && right_stack.peek() <= arr[j])
                right_stack.pop();
            left_stack.push(arr[i]);
            right_stack.push(arr[j]);
        }
        for(int i=0;i<n;i++)
            System.out.print(left_count[i]+right_count[i]+1 + " ");
        System.out.println();
}

算法真题-腾讯-逛街