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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/stack/mono-stack/84.-largest-rectangle-in-histogram.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.