逛街

问题描述
小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。

小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

输入描述：
输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字wi(1<=i<=n)，代表每一栋楼的高度。
1<=n<=100000;
1<=wi<=100000;

输出描述：

输出一行，包含空格分割的n个数字vi，分别代表小Q在第i栋楼时能看到的楼的数量。

输入例子：

6
5 3 8 3 2 5

输出例子：
3 3 5 4 4 4

例子说明：
当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。
当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。

单调栈

import java.util.*;

public class Main{
    
     public static int[] maxVisit(int[] nums, int len){
        int[] ans = new int[len];
        Arrays.fill(ans, 1);
        Stack<Integer> stDes = new Stack<>();
        //计算看左边能看到的值
        for(int i = 0; i < len; i++){
            if(stDes.isEmpty()){
                stDes.push(nums[i]);
            }else if(!stDes.isEmpty() && nums[i] <= stDes.peek()){
                ans[i] += stDes.size();
                stDes.push(nums[i]);
            }else{
                //单调减少栈
                while(!stDes.isEmpty() && nums[i] > stDes.peek()){
                    stDes.pop();
                    ans[i] ++;
                }
                //遇到第一个大于等于的，也算是能看见，故+1
                if(!stDes.isEmpty()){
                    ans[i] ++;
                }
                stDes.push(nums[i]);
            }
        }
        // System.out.println(Arrays.toString(ans));

        stDes.clear();
        for(int i = len-1; i >= 0; i--){
            if(stDes.isEmpty()){
                stDes.push(nums[i]);
            }else if(!stDes.isEmpty() && nums[i] <= stDes.peek()){
                ans[i] += stDes.size();
                stDes.push(nums[i]);
            }else{
                //单调减少栈
                while(!stDes.isEmpty() && nums[i] > stDes.peek()){
                    stDes.pop();
                    ans[i] ++;
                }
                //遇到第一个大于等于的，也算是能看见，故+1
                if(!stDes.isEmpty()){
                    ans[i] ++;
                }
                stDes.push(nums[i]);
            }
        }

        return ans;
    }
    
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int len = in.nextInt();
            int[] nums = new int[len];
            for(int i = 0; i < len; i++){
                nums[i] = in.nextInt();
            }
            // System.out.println(Arrays.toString(maxVisit(nums,len)));
            int[] ans = maxVisit(nums,len);
            for(int i = 0; i < ans.length; i++){
                System.out.print(ans[i] + " ");
            }
            System.out.println();
        }
    }

   
}