# 84. Largest Rectangle in Histogram

[Link](https://leetcode.com/problems/largest-rectangle-in-histogram/)

**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;
    }
```
