> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/stack/wei-chi-di-zeng-huo-di-jian/largest-rectangle-in-histogram.md).

# 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)