solution.md

# 最大矩形

<p>给定一个仅包含 <code>0</code> 和 <code>1</code> 、大小为 <code>rows x cols</code> 的二维二进制矩阵，找出只包含 <code>1</code> 的最大矩形，并返回其面积。</p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0085.Maximal%20Rectangle/images/maximal.jpg" style="width: 402px; height: 322px;" /><pre><strong>输入：</strong>matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]<strong><br />输出：</strong>6<strong><br />解释：</strong>最大矩形如上图所示。</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>matrix = []<strong><br />输出：</strong>0</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>matrix = [["0"]]<strong><br />输出：</strong>0</pre><p><strong>示例 4：</strong></p><pre><strong>输入：</strong>matrix = [["1"]]<strong><br />输出：</strong>1</pre><p><strong>示例 5：</strong></p><pre><strong>输入：</strong>matrix = [["0","0"]]<strong><br />输出：</strong>0</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>rows == matrix.length</code></li>	<li><code>cols == matrix[0].length</code></li>	<li><code>0 <= row, cols <= 200</code></li>	<li><code>matrix[i][j]</code> 为 <code>'0'</code> 或 <code>'1'</code></li></ul>
<p>以下错误的选项是？</p>

## aop

### before

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

```cpp
int main()
{
    Solution sol;
    vector<vector<char>> matrix = {{'1', '0', '1', '0', '0'},
                                   {'1', '0', '1', '1', '1'},
                                   {'1', '1', '1', '1', '1'},
                                   {'1', '0', '0', '1', '0'}};
    int res;
    res = sol.maximalRectangle(matrix);
    cout << res << endl;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        stack<int> h;
        heights.push_back(0);
        int ans = 0, hsize = heights.size();
        for (int i = 0; i < hsize; i++)
        {
            while (!h.empty() && heights[h.top()] > heights[i])
            {
                int top = h.top();
                h.pop();
                ans = max(ans, heights[top] * (h.empty() ? i : (i - h.top())));
            }
            h.push(i);
        }
        return ans;
    }

    int maximalRectangle(vector<vector<char>> &matrix)
    {
        if (matrix.empty())
            return 0;
        int n = matrix.size(), m = matrix[0].size(), ans = 0;
        vector<vector<int>> num(n, vector<int>(m, 0));
        for (int j = 0; j < m; j++)
        {
            num[0][j] = (matrix[0][j] == '0') ? 0 : 1;
            for (int i = 1; i < n; i++)
                num[i][j] = (matrix[i][j] == '0') ? 0 : num[i - 1][j] + 1;
        }
        for (int i = 0; i < n; i++)
        {
            int area = largestRectangleArea(num[i]);
            ans = max(ans, area);
        }
        return ans;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int maximalRectangle(vector<vector<char>> &matrix)
    {
        int res = 0;
        vector<int> height;
        for (int i = 0; i < matrix.size(); ++i)
        {
            height.resize(matrix[i].size());
            for (int j = 0; j < matrix[i].size(); ++j)
            {
                height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);
            }
            res = max(res, largestRectangleArea(height));
        }
        return res;
    }

    int largestRectangleArea(vector<int> &heights)
    {
        if (heights.empty())
            return 0;
        stack<int> st;
        heights.push_back(0);
        int res0 = 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() - 1;
                if (width * curHeight > res0)
                    res0 = width * curHeight;
            }
            st.push(i);
        }
        return res0;
    }
};
```

### B

```cpp
class Solution
{
public:
    int maximalRectangle(vector<vector<char>> &matrix)
    {
        if (matrix.size() == 0)
        {
            return 0;
        }
        int m = matrix.size();
        int n = matrix[0].size();
        int left[n];
        int right[n];
        int height[n];

        memset(right, n, sizeof(right));
        memset(left, n, sizeof(left));
        memset(height, n, sizeof(height));

        int maxarea = 0;
        for (int i = 0; i < m; ++i)
        {
            int cur_left = 0, cur_right = n;

            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == '1')
                {
                    height[j]++;
                }
                else
                {
                    height[j] = 0;
                }
            }

            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == '1')
                {
                    left[j] = max(left[j], cur_left);
                }
                else
                {
                    left[j] = 0, cur_left = j + 1;
                }
            }

            for (int j = n - 1; j >= 0; --j)
            {
                if (matrix[i][j] == '1')
                {
                    right[j] = min(right[j], cur_right);
                }
                else
                {
                    right[j] = n;
                    cur_right = j;
                }
            }

            for (int j = 0; j < n; ++j)
            {
                maxarea = max(maxarea, (right[j] - left[j]) * height[j]);
            }
        }
        return maxarea;
    }
};
```

### C

```cpp
class Solution
{
public:
    int maximalRectangle(vector<vector<char>> &matrix)
    {
        if (matrix.size() == 0)
        {
            return 0;
        }
        int maxarea = 0;
        int dp[matrix.size()][matrix[0].size()];
        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < matrix.size(); ++i)
        {
            for (int j = 0; j < matrix[0].size(); ++j)
            {
                if (matrix[i][j] == '1')
                {
                    dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
                    int width = dp[i][j];

                    for (int k = i; k >= 0; k--)
                    {
                        width = min(width, dp[k][j]);
                        maxarea = max(maxarea, width * (i - k + 1));
                    }
                }
            }
        }
        return maxarea;
    }
};
```