# 84. Largest Rectangle in Histogram

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
```

## Thoughts

<http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html>

给不同高度的histogram，问能形成的最大长方形面积。暴力法是对i，遍历其前面直到比它矮的，这段长度再乘以i的高即以i为底能形成的面积最大长方形；同理再遍历其后面，最后两段面积相加。也就是说想知道i前面有多少连续比它高的，而且这段元素在给i之后的作左边元素时高度都受限于h\[i]。维护以高度为评判的递增序列，用stack，里头存index，当遇到高度比栈顶小的height\[i]就弹出，计算它的index与i的距离 (宽, 因为这些元素都是比当前栈顶高的, 能以栈顶的高度形成面积), 再乘以它的高度即这个块能形成的最大面积。

![](/files/-MBU7IEZ-RH_0O5_LcjP)

## Code

```python
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        s, res = [], 0
        heights.append(0)
        for i, h in enumerate(heights):
            while len(s) > 0 and h < heights[s[-1]]:
                hei = heights[s[-1]]
                s.pop()
                wid = i - s[-1] - 1 if len(s) > 0 else i
                res = max(res, hei * wid)
            s.append(i)
        return res
```

```java
/*
 * @lc app=leetcode id=84 lang=cpp
 *
 * [84] Largest Rectangle in Histogram
 */
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> ind;
        heights.push_back(0);
        int res = 0;
        for (int i = 0; i < heights.size(); ++i) {
            while (!ind.empty() && heights[ind.top()] > heights[i]) {
                const int h = heights[ind.top()];
                ind.pop();
                const int w = ind.empty() ? i : i - ind.top() - 1;
                res = max(res, h * w); 
            }
            ind.push(i);
        }
        return res;
    }
};


```

## Analysis

时空复杂度O(n).\
注意heights最后一个要是0, 确保能正确弹出所有元素.\
还有int w = stack.isEmpty() ? i : (i - stack.peek() - 1)


---

# 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://hao-fu-1.gitbook.io/oj/stack/wei-chi-di-zeng-huo-di-jian/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.