腾讯笔试--逛街

image

主要的知识点是：单调栈,该题牢牢记得：栈中记录当前楼能看到的元素

image

单调栈是单调递增栈，栈顶是最小值
单调栈存的是能看到的楼
向左看：
从0开始遍历元素
首先取leftstack的大小作为向左看的值
分情况讨论：
（1）如果leftstack为empty（），则：
```
leftstack.push(heights[i]);

                   ```
            (2)如果leftstack不为empty（），且当前楼小于栈中最小元素，表明当前楼可以被下一层楼看到，入栈：
                ```
                           leftstack.push(heights[i]);
      
                ```
                (3)如果leftstack不为empty（），且当前楼大于于栈中最小元素，代表当前楼把栈顶元素遮住了，看不到栈顶元素，所以将栈顶弹出，继续比较，直到当前楼小于栈中最小元素，然后再将当前楼入栈
        ```
           while(!leftstack.isEmpty()&&heights[i]>=leftstack.peek()){
                     leftstack.pop();
              }
              leftstack.push(heights[i]);
        
      ```

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型一维数组
     */
    public int[] findBuilding (int[] heights) {
        // write code here
        //单调栈是单调递增栈，栈顶是最小值
        //单调栈存的是能看到的楼
        
        int n=heights.length;
        int [] res=new int[n];
        Stack<Integer> leftstack=new Stack<Integer>();
        Stack<Integer> rightstack=new Stack<Integer>();
        for(int i=0;i<n;i++){//向左看,i就代表当前所处的楼
            res[i]=leftstack.size();//取得左边能看到楼的数目
            //如果当前楼大于栈中最小值，就将栈顶弹出
            //代表当前楼的高度已经遮住最小值，所以看不到了，所以需要将小于当前楼的
            //值弹出，代表已经看不到了，这是为下一次看来做准备
            //我们需要去更新当前楼
            while(!leftstack.isEmpty()&&heights[i]>=leftstack.peek()){
                leftstack.pop();
            }
            leftstack.push(heights[i]);
        }
        for(int j=n-1;j>=0;j--){//向右看
            res[j]=res[j]+rightstack.size()+1;
            while(!rightstack.isEmpty()&&heights[j]>=rightstack.peek()){
                rightstack.pop();
            }
            rightstack.push(heights[j]);
        }
        return res;
    }
}