腾讯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; } }