腾讯9-17笔试笔记

都是泪，第4题感觉能写出来又没写出来，时间紧迫写了个暴力求解的，时间复杂度过高只通过50%。现在回顾一下，省略绞尽脑汁的大段过程，应该是用单调栈来解的吧，有想法或知道正确解法的还望不吝赐教啊。
先回顾下题目：n个高楼排成一行，求从每个高楼能看到的楼数量（前面楼的高度大于等于后面楼的高度时，后面的楼将被挡住）
输入：第一行 数字n 表示多少栋楼，第二行 n个数字，按顺序表示每栋楼的高度Wi
(1<=n<=100000;1<=Wi<=100000)
输出：一行，包含空格分割的n个数字Vi，代表在i位置时能看到的楼数量
例：
输入：6
5 3 8 3 2 5
输出：3 3 5 4 4 4
说明：站在位置3时，向前看到位置1、2，向后看到为止4、6加上自身的楼共5个，站在位置4时，向前看到位置3，想后看到位置5、6，加上自身位置共4处。
单调栈解法代码：

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }
        in.close();

        //对左右分开处理
        List<Integer> left = left(getLeft(arr));
        List<Integer> right = right(getRight(arr));

        List<Integer> all = new ArrayList<Integer>();
        for (int i = 0, temp = 0; i < left.size(); i++) {
            temp = left.get(i) + 1 + right.get(i);
            all.add(temp);
            System.out.print(temp + " ");
        }
    }
    //辅助函数
    public static List<Integer> left(int[] res) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(0);
        for (int i = 0; i < res.length - 1; i++) {
            list.add(res[i]);
        }
        return list;
    }

    public static List<Integer> right(int[] res) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i < res.length; i++) {
            list.add(res[i]);
        }
        list.add(0);
        return list;
    }

    //单调栈实现求解
    public static int[] getLeft(int[] arr) {
        int[] result = new int[arr.length];
        Stack<Integer> upStack = new Stack<Integer>();
        upStack.push(Integer.MIN_VALUE);
        for (int i = 0; i < arr.length; i++) {
            while (!upStack.isEmpty() && arr[i] >= upStack.peek()) {
                upStack.pop();
            }
            upStack.push(arr[i]);
            result[i] = upStack.size();//当前栈内数量即为i+1位置向左看到楼的数量
        }
        return result;
    }

    public static int[] getRight(int[] arr) {
        int L = arr.length;
        int[] result = new int[L];
        Stack<Integer> upStack = new Stack<Integer>();
        upStack.push(Integer.MIN_VALUE);
        for (int i = 0; i < L; i++) {
            while (!upStack.isEmpty() && arr[L - 1 - i] >= upStack.peek()) {
                upStack.pop();
            }
            upStack.push(arr[L - 1 - i]);
            result[L - 1 - i] = upStack.size();
        }
        return result;
    }
}