leetcode 链接：最大矩形

题目

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例：
[困难] 85. 最大矩形 - 图1

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

输入：matrix = []
输出：0

输入：matrix = [["0"]]
输出：0

输入：matrix = [["1"]]
输出：1

输入：matrix = [["0","0"]]
输出：0

代码 & 解答

解法一：使用柱状图的优化暴力方法

参考 leetcode链接：84. 柱状图中最大的矩形

设矩阵行数为 m，列数为 n，则

时间复杂度为 O()

空间复杂度为 O(mn)

class Solution {
public:
  int maximalRectangle(vector<vector<char>>& matrix) {
      int maxArea = 0;

      // 1. 求出矩阵中每个元素左边连续 1 的个数（包含这个元素本身），存储在 left 中
      int rows = matrix.size();
      if(rows == 0)
          return 0;
      int cols = matrix[0].size();
      if(cols == 0)
          return 0;
      vector<vector<int>> left(rows, vector<int>(cols, 0));    // 存储矩阵每个元素左边连续 1 的个数（包含这个元素本身）
      for(int i = 0; i < rows; ++i)
      {
          left[i][0] = matrix[i][0] == '1' ? 1 : 0;
          for(int j = 1; j < cols; ++j)
              left[i][j] = matrix[i][j] == '1' ? left[i][j - 1] + 1 : 0;
      }

      // 2. 对于矩阵中每个元素，枚举以其为右下角的全 1 矩阵并计算面积
      for(int i = 0; i < rows; ++i)
      {
          for(int j = 0; j < cols; ++j)    // 遍历矩阵中每个元素
          {
              int width = left[i][j];
              for(int height = 1; i - height + 1 >= 0 && left[i - height + 1][j] > 0; ++height)     // 向上遍历高度
              {
                  width = left[i - height + 1][j] < width ? left[i - height + 1][j] : width;
                  int area = width * height;
                  maxArea = area > maxArea ? area : maxArea;
              }
          }
      }

      return maxArea;
  }
};

执行结果： ``` 执行结果：通过

执行用时：44 ms, 在所有 C++ 提交中击败了 45.37% 的用户内存消耗：11.2 MB, 在所有 C++ 提交中击败了 88.60% 的用户

<a name="wgGaK"></a>
## 解法二：单调栈
针对解法一优化，第一步不变，第二步改用单调栈的思想，最终时间复杂度 O(mn)，空间复杂度 O(mn)

方法：

1. 先求出矩阵 `matrix` 中每个元素左边连续 1 的个数（包含这个元素本身），存储在矩阵 `left` 中
1. 遍历矩阵 `left` 的每一列，对每一列就相当于求一次 [[困难] 84. 柱状图中最大的矩形](https://www.yuque.com/docs/share/f7e15f55-b103-4157-8c29-329807d7ea7b?# 《[困难] 84. 柱状图中最大的矩形》) ：对于列 `col`，该列的每个元素的值就相当于柱子的高度，以这个高度作为矩形的高，只需找到这个高度向上、向下能扩展的宽度（使用单调栈，求出该列每个元素上边高度小于当前柱子高且最近的行号、求出该列每个元素下边高度小于当前柱子高且最近的行号），就可以求出以该高度为高的矩形的面积。步骤如下：
   1. 对于当前列 `col`，使用单调栈，求出每根柱子上、下两侧比他矮且离得最近的柱子的行号，分别存储在数组  `up`、`down` 中
   1. 遍历该列的每行，求出以每个元素（柱子高度）为高对应的矩形面积，如果大于最大面积，就更新最大面积的值

![image.png](https://cdn.nlark.com/yuque/0/2021/png/1324638/1623851066864-f3618989-680e-4b7d-a7d4-73f86c1eec99.png#clientId=u1eeecaf2-f28c-4&from=paste&height=678&id=u7579ec34&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1356&originWidth=1964&originalType=binary&ratio=2&size=542145&status=done&style=none&taskId=u5e215228-42d2-46a5-b59e-b5294ac0dac&width=982)
```cpp
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int maxArea = 0;

        // 1. 先求出矩阵 matrix 中每个元素左边连续 1 的个数（包含这个元素本身），存储在矩阵 left 中
        int rows = matrix.size();
        if(rows == 0)
            return 0;
        int cols = matrix[0].size();
        if(cols == 0)
            return 0;
        vector<vector<int>> left(rows, vector<int>(cols, 0));
        for(int row = 0; row < rows; ++row)
        {
            left[row][0] = matrix[row][0] == '1' ? 1 : 0;
            for(int col = 1; col < cols; ++col)
                left[row][col] = matrix[row][col] == '1' ? left[row][col - 1] + 1 : 0;
        }

        // 2. 遍历矩阵 left 的每一列，对每一列就相当于求一次柱状图中的最大矩形
        for(int col = 0; col < cols; ++col)
        {
            // 2.1 使用单调栈，求出当前列每根柱子（每行元素）上、下两侧比他矮且离得最近的柱子的行号，分别存储在数组  up、down 中
            vector<int> up(rows, 0);
            vector<int> down(rows, 0);
            stack<vector<int>> s;
            for(int row = 0; row < rows; ++row)
            {
                while(!s.empty() && left[row][col] < left[s.top().back()][col])
                {
                    vector<int> top = s.top();
                    s.pop();
                    for(auto it = top.begin(); it != top.end(); ++it)
                    {
                        up[*it] = s.empty() ? -1 : s.top().back();
                        down[*it] = row;
                    }
                }
                if(!s.empty() && left[row][col] == left[s.top().back()][col])
                    s.top().push_back(row);
                else
                    s.push(vector<int>(1, row));
            }
            while(!s.empty())
            {
                vector<int> top = s.top();
                s.pop();
                for(auto it = top.begin(); it != top.end(); ++it)
                {
                    up[*it] = s.empty() ? -1 : s.top().back();
                    down[*it] = rows;
                }
            }

            // 2.2 求出以该列每行元素（柱子高度）为高对应的矩形面积，如果大于最大面积，就更新最大面积的值
            for(int row = 0; row < rows; ++row)
            {
                int width = down[row] - up[row] -1;
                int area = width * left[row][col];
                maxArea = area > maxArea ? area : maxArea;
            }
        }

        return maxArea;
    }
};

执行结果：

执行结果：通过

执行用时：112 ms, 在所有 C++ 提交中击败了 5.54% 的用户
内存消耗：19.8 MB, 在所有 C++ 提交中击败了 5.04% 的用户