> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/stack/mono-stack/84.-largest-rectangle-in-histogram.md).

# 84. Largest Rectangle in Histogram ( mono increasing stack

<https://leetcode.com/problems/largest-rectangle-in-histogram/>

![](/files/-MC03Phnghnim1UhPvHQ)

## naive

T: O(n^2)

```java
// 第二想到固定某柱子, 背向雙指針, 找左右邊界(找比自己高的), 求面積
class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int n = heights.length;
        for (int i = 0; i < n ; i++) {
            int curr = heights[i];
            int left = i-1;
            int right = i+1;
            while (left >= 0 && heights[left] >= curr) {
                left--;
            }
            while (right < n && heights[right] >= curr) {
                right++;
            }
            max = Math.max(max, curr*(right - left - 1));
        }
        return max;
    }
}
```

## mono stack

h = heights\[stack.pop()];  =>   7

2 - 0 - 1

i - stack.peek() - 1

area = 7 \* (2 - 0 - 1) &#x20;

```java
while (!stack.isEmpty() && heights[stack.peek()] >= cur) { // find right bound
    int h = heights[stack.pop()]; // one by one pop to use height to cal the area
    int w = stack.isEmpty() ? i : i - stack.peek() - 1; // 2 - 0 - 1
    ans = Math.max(ans, h * w);
} 
```

O(n), O(n)

```java
class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        
        int ans = 0;
        for (int i = 0; i <= heights.length; i++) {
            int cur = (i == heights.length) ? -1 : heights[i];
            
            while (!stack.isEmpty() && heights[stack.peek()] >= cur) { // find right bound
                int h = heights[stack.pop()]; // one by one pop to use height to cal the area
                int w = stack.isEmpty() ? i : i - stack.peek() - 1; // 2 - 0 - 1
                ans = Math.max(ans, h * w);
            } 
            stack.push(i);
        }
        return ans;
    }
}
```

## readable version

i = heights.lenght , cur 設定成 -1, 用意在讓stack剩下的 pop()完(退棧）

heights\[stack.peek()] >= cur   =>   一定 >= -1,&#x20;

stack 空的時候, leftBound = -1, or stack.peek()

這樣才能算到比較低的那根到左邊界所有的面積&#x20;

```
int rightBound = i;
int leftBound = stack.isEmpty() ? -1 : stack.peek();
```

2\.     2

&#x20;    1&#x20;

2會先退掉 (1比較小

&#x20;         2

&#x20;    1

到底才開始退(右邊界-1了

2退掉

1退掉, 此時stack 空了, 代表可以算左邊界 -1了

```java
class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
    
        // stack to record index,
        // for i = 0 ~ heights.length
        // while cur >= peek(), means find right bound = i, 
        // so pop h, get w, 
        // if stack is empty, means left bound is -1, or left bound is stack.peek()
        // cal area
        // push
        
        int max = 0;
        for (int i = 0; i <= heights.length; i++) {
            int cur = (i == heights.length) ? -1 : heights[i];
            
            while (!stack.isEmpty() && heights[stack.peek()] >= cur) {
                int h = heights[stack.pop()];
                int rightBound = i;
                int leftBound = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, h*(rightBound - leftBound - 1));
            }
            stack.push(i);
        }
        return max;
    }
}
```

## newest version

```java
class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        int max = Integer.MIN_VALUE;
        // 因為是要左邊界右邊界, 所以要執行到 height的尾巴  i <= heights.length
        for (int i = 0; i <= heights.length; i++) { // why <= heights.length
            int curr = (i == heights.length) ? -1 : heights[i];
            
            while (!stack.isEmpty() && curr <= heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int rightBound = i;
                int leftBound = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, h*(rightBound - leftBound - 1));
            }
            stack.push(i);
        }
        return max;
    }
}
```