solution.md

# 柱状图中最大的矩形

<p>给定 <em>n</em> 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。</p><p>求在该柱状图中，能够勾勒出来的矩形的最大面积。</p><p>&nbsp;</p><p><img src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0084.Largest%20Rectangle%20in%20Histogram/images/histogram.png"></p><p><small>以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为&nbsp;<code>[2,1,5,6,2,3]</code>。</small></p><p>&nbsp;</p><p><img src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0084.Largest%20Rectangle%20in%20Histogram/images/histogram_area.png"></p><p><small>图中阴影部分为所能勾勒出的最大矩形面积，其面积为&nbsp;<code>10</code>&nbsp;个单位。</small></p><p>&nbsp;</p><p><strong>示例:</strong></p><pre><strong>输入:</strong> [2,1,5,6,2,3]<strong><br />输出:</strong> 10</pre>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c
int main()
{
    Solution sol;
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    int res;
    res = sol.largestRectangleArea(heights);
    cout << res << endl;
    return 0;
}
```

## 答案

```c
class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        if (heights.empty())
            return 0;
        stack<int> st;
        heights.push_back(0);
        int res = 0;
        for (int i = 0; i < heights.size(); i++)
        {
            while (!st.empty() && heights[i] < heights[st.top()])
            {
                int curHeight = heights[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top();
                if (width * curHeight > res)
                    res = width * curHeight;
            }
            st.push(i);
        }
        return res;
    }
};
```
## 选项


### A

```c
class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        int sz = heights.size();
        int ma = 0;
        for (int i = 0; i < sz; i++)
        {
            int len = 1;
            int hei = heights[i];
            int sta = i - 1, en = i + 1;
            while (sta >= 0 && heights[sta] >= hei)
            {
                len++;
                sta--;
            }
            while (en < sz && heights[en] >= hei)
            {
                len++;
                en++;
            }
            ma = max(ma, len * hei);
        }
        return ma;
    }
};
```

### B

```c
class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        int n = heights.size();

        vector<int> left(n), right(n, n);

        stack<int> mono_stack;

        for (int i = 0; i < n; ++i)
        {

            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i])
            {
                right[mono_stack.top()] = i;
                mono_stack.pop();
            }

            left[i] = (mono_stack.empty() ? -1 : mono_stack.top());

            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i)
        {

            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};
```

### C

```c
class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        int n = heights.size();
        stack<int> index;
        int area = 0;
        for (int i = 0; i < heights.size(); i++)
        {
            if (index.empty() || heights[index.top()] < heights[i])
                index.push(i);
            else
            {
                while (!index.empty() && heights[index.top()] >= heights[i])
                {
                    int tmp = index.top();
                    index.pop();
                    int length = 0;
                    if (index.empty())
                        length = i;
                    else
                        length = i - index.top() - 1;
                    area = max(area, length * heights[tmp]);
                }
                index.push(i);
            }
        }
        while (!index.empty())
        {
            int tmp = index.top();
            index.pop();
            int length = 0;
            if (index.empty())
                length = n;
            else
                length = n - index.top() - 1;
            area = max(area, length * heights[tmp]);
        }
        return area;
    }
};
```