84. Largest Rectangle in Histogram

Link

Solution

針對每個element i 找出 i-1 -> 0 之間 第一個小於 heights[i]的 , ie : lessFromLeft[i] 針對每個element i 找出 i+1 -> len-1 之間 第一個小於 heights[i]的 , ie : lessFromRight[i]

那麼結果max就可以輕易取得:

        int max = 0;
        for(int i = 0; i < heights.length; i++){
            max = Math.max(max, heights[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
        }
        return max;

接下來就是如何有效地取得lessFromRight , lessFromLeft

只要reuse之前找到的lessFromRight/Left來計算， 以lessFromLeft為例，當 height[p] >= height[i] where p < i，那麼lessFromLeft[i]一定也可以被lessFromLeft[p]滿足

        for(int i = 1; i < heights.length; i++){
            int p = i-1;
            while(p >= 0 && heights[p] >= heights[i]){
                p = lessFromLeft[p];
            }
            lessFromLeft[i] = p;
        }
        
        for(int i = heights.length -2; i >= 0; i--){
            int p = i + 1;
            while(p < heights.length && heights[p] >= heights[i]){
                p = lessFromRight[p];
            }
            lessFromRight[i] = p;
        }

  public int largestRectangleArea(int[] heights) {
        if(heights.length == 0) return 0;
        int[] lessFromRight = new int[heights.length];
        int[] lessFromLeft = new int[heights.length];
        lessFromRight[heights.length-1] = heights.length;
        lessFromLeft[0] = -1;
        
        for(int i = 1; i < heights.length; i++){
            int p = i-1;
            while(p >= 0 && heights[p] >= heights[i]){
                p = lessFromLeft[p];
            }
            lessFromLeft[i] = p;
        }
        
        for(int i = heights.length -2; i >= 0; i--){
            int p = i + 1;
            while(p < heights.length && heights[p] >= heights[i]){
                p = lessFromRight[p];
            }
            lessFromRight[i] = p;
        }
        
        
        int max = 0;
        for(int i = 0; i < heights.length; i++){
            max = Math.max(max, heights[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
        }
        return max;
    }