# 84. Largest Rectangle in Histogram

[Link](https://leetcode.com/problems/maximal-rectangle/description/)

Given *n* non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

![](https://assets.leetcode.com/uploads/2018/10/12/histogram.png)\
Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.

![](https://assets.leetcode.com/uploads/2018/10/12/histogram_area.png)\
The largest rectangle is shown in the shaded area, which has area = `10` unit.

**Example:**

```
Input: [2,1,5,6,2,3]
Output: 10
```

**Solution**

這題用stack的方式去找出所有可能矩形的right, left邊界。

作法很tricky。

巡迴arrays中的所有元素，依序擺入stack中，並確保裡面是升序的元素值。當巡迴到不是升序的元素，無法擺入stack就以stack.peek()所指的位置(ex. index) 的元素為**高**開始進行找right , left的動作，&#x20;

已知 heights\[index] > heights\[left]，&#x20;

height\[index] > height\[right]

left <= index <= right

**寬**就是 right - left - 1

![](https://2628390332-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M0RnkuvOeqe0clAIN1b%2F-M4h0KUFHuqq3rbUrLEI%2F-M4h3M2USJjS4rPke-b8%2Fimage.png?alt=media\&token=49ced5e0-ea84-4726-96da-ec6502d1112c)

```
public int find(int heights[]){

    if(heights == null || heights.length == 0) return 0;
    Stack<Integer> s = new Stack<>();
    for(int i = 0; i <= heights.length; i++){
        int value = (i == heights.length) ? 0 : heights[i];
        if(s.isEmpty() || heights[s.peek()] <= value){
            s.push(i);
        }
        else{
            int height = heights[s.pop()];
            int right = i;
            int left = s.isEmpty() ? -1 : s.peek();
            maxValue = Math.max(maxValue, height * (right - left - 1));
            i--;
        }
    }
    return maxValue;

}
```
