题解 | #逛街#

1.栈优化

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型一维数组
     */
    public int[] findBuilding (int[] heights) {
        int n = heights.length;
        int[] res = new int[n];
        int[] left = new int[n];
        int[] right = new int[n];

        Stack<Integer> l_stack = new Stack<>();
        Stack<Integer> r_stack = new Stack<>();
        l_stack.push(Integer.MAX_VALUE);
        r_stack.push(Integer.MAX_VALUE);

        // i+1 从右向左看 0-i
        for(int i=0;i<n-1;i++){
            // 最开始没加等号 因为相等会覆盖 所以例如 8,8 也要弹出一个8来
            while(heights[i]>=l_stack.peek()) l_stack.pop();
            l_stack.push(heights[i]);
            left[i+1] = l_stack.size()-1;

        }
        // i-1 从左向右看 i-length
        for(int i=n-1;i>0;i--){
            while(heights[i]>=r_stack.peek()) r_stack.pop();
            r_stack.push(heights[i]);
            right[i-1] = r_stack.size()-1;
        }

        for (int i=0;i<n;i ++){
            res[i] = left[i] + right[i] + 1;
        }
        return res;
    }
}

2.双重循环
O(n^2) 只能过50%

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型一维数组
     */    public int[] findBuilding (int[] heights) {
        int n = heights.length;
        int[] res = new int[n];

        for(int i=0;i<n;i++){
            // 从left 看向right
            int max_left = -1;
            int res_left = 0;
            for(int j=i+1;j<n;j++){
                if(heights[j] > max_left){
                    res_left++;
                    max_left = heights[j];
                }
            }

            // 从 right 看向right
            int max_right = -1;
            int res_right = 0;
            for(int j=i-1;j>=0;j--){
                if(heights[j] > max_right){
                    res_right++;
                    max_right = heights[j];
                }
            }
            res[i] = res_left + res_right +1;
        }
        return res;
    }
}