騰訊2020校招筆試題 逛街 JAVA題解

逛街

小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棟樓。      

思路：經典單調棧問題。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Stack;
public class Main{
	static final int N = 100005;
	static int []arr = new int [N];
	static int []cnt = new int [N];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int n = Integer.parseInt(reader.readLine());
		String []split = reader.readLine().split(" ");
		for(int i = 1;i <= n;i ++) {
			arr[i] = Integer.parseInt(split[i-1]);
		}
		Stack<Integer> Lstk = new Stack<>();
		for(int i = 1;i <= n;i ++) {
			cnt[i] += Lstk.size();
			while(!Lstk.isEmpty() && arr[i] >= Lstk.peek()) Lstk.pop();
			Lstk.add(arr[i]);
		}
		Stack<Integer> Rstk = new Stack<>();
		for(int i = n;i >= 1;i --) {
			cnt[i] += Rstk.size();
			while(!Rstk.isEmpty() && arr[i] >= Rstk.peek()) Rstk.pop();
			Rstk.add(arr[i]);
		}
		for(int i = 1;i <= n;i ++) {
			if(i == n) pw.println(cnt[i] + 1);
			else pw.print(cnt[i] + 1 + " ");
		}
		pw.flush();
		pw.close();
		reader.close();
	}
}