本題的鏈接是：逛街

題目描述

小Q在周末的時候和他的小伙伴來到大城市逛街，一條步行街上有很多高樓，共有n座高樓排成一行。
小Q從第一棟一直走到了最后一棟，小Q從來都沒有見到這么多的樓，所以他想知道他在每棟樓的位置處能看到多少棟樓呢？（當(dāng)前面的樓的高度大于等于后面的樓時，后面的樓將被擋?。?/p>

輸入描述:

輸入第一行將包含一個數(shù)字n，代表樓的棟數(shù)，接下來的一行將包含n個數(shù)字wi(1<=i<=n)，代表每一棟樓的高度。
1<=n<=100000;
1<=wi<=100000;

輸出描述:

輸出一行，包含空格分割的n個數(shù)字vi，分別代表小Q在第i棟樓時能看到的樓的數(shù)量。

輸入例子1:

6
5 3 8 3 2 5

輸出例子1:

3 3 5 4 4 4

例子說明1:

當(dāng)小Q處于位置3時，他可以向前看到位置2,1處的樓，向后看到位置4,6處的樓，加上第3棟樓，共可看到5棟樓。當(dāng)小Q處于位置4時，他可以向前看到位置3處的樓，向后看到位置5,6處的樓，加上第4棟樓，共可看到4棟樓。

解題思路1-暴力法

一開始用到的方法是簡單粗暴的暴力法，結(jié)果只有60%的測試用例通過，時間復(fù)雜度是，明顯不符合題意。

代碼

    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;
//        輸入數(shù)據(jù)
        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();
    }

思路分析:

可以用到單調(diào)棧，顧名思義就是棧里面的元素是單調(diào)遞增的，這樣的話只要判斷元素是否大于棧里面的元素就可以進行判斷有多少棟樓比當(dāng)前的樓高。
例如：
5 3 8 3 2 5
我們用一個向前看的棧Stack進行說明，他是個單調(diào)棧，里面所有的元素都是遞增的，用數(shù)組left表示向前看有多少樓可以看到，例如left[1]=1表示在位置1向左邊看可以看到1棟樓。
遍歷數(shù)組：
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）

單調(diào)棧代碼

    public static void main(String[] args) {
    // write your code here
//        用戶輸入數(shù)據(jù)
        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<>();

//        向左看和向右看的樓的數(shù)量
        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();
//            如果當(dāng)前的數(shù)字比棧頂?shù)臄?shù)字還要大的話，就出棧，因為已經(jīng)被擋住了
            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();
}