题目

给定一个仅包含 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

解答 & 代码

解法一：

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();
        // 1. 求出矩阵中每个元素右边连续 1 的个数（包含这个元素本身），存储在 right1Len 中
        vector<vector<int>> right1Len(rows, vector<int>(cols, 0));
        for(int i = 0; i < rows; ++i)
        {
            right1Len[i][cols - 1] = matrix[i][cols - 1] == '1' ? 1 :0;
            for(int j = cols - 2; j >= 0; --j)
                right1Len[i][j] = matrix[i][j] == '0' ? 0 : right1Len[i][j + 1] + 1;
        }
        int result = 0;
        // 2. 遍历矩阵中每个元素，枚举以其为左下角的全 1 矩阵并计算面积
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                if(matrix[i][j] == '1')
                {
                    int width = right1Len[i][j];
                    for(int height = 1; i - height + 1 >= 0; ++height)
                    {
                        width = min(width, right1Len[i - height + 1][j]);
                        int curArea = width * height;
                        result = max(result, curArea);
                    }
                }
            }
        }
        return result;
    }
};

复杂度分析：设矩阵行数为 m，列数为 n

时间复杂度：遍历矩阵中的每个元素，时间复杂度 O(mn)。对于每个元素，以其为全 1 矩阵左下角，往上遍历不同的高度，求所以以其为左下角的矩形面积，时间复杂度 O(m)
空间复杂度 O(mn)：right1Len 矩阵的空间复杂度

执行结果：

执行结果：通过
执行用时：140 ms, 在所有 C++ 提交中击败了 5.30% 的用户
内存消耗：12.6 MB, 在所有 C++ 提交中击败了 77.80% 的用户

解法二：单调栈

解法一对于矩阵中的每个元素，都要向上遍历不同的高度，求所以以其为左下角的矩形面积，增加了一个 O(m) 的时间复杂度。

求出矩阵中每个元素右边连续 1 的个数（包含这个元素本身），存储在二维矩阵 right1Len 中

遍历 right1Len 矩阵的每一列

单调栈，求出每个元素下边最近的比它小的元素下标，存储在 down
单调栈，求出每个元素上边最近的比它小的元素下标，存储在 up

以每个元素的值（右边连续 1 的个数）为高度，down[i] - up[i] - 1 作为宽度，求得矩形面积，与最大矩形面积比较，更新最大矩形面积

class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
  if(matrix.size() == 0 || matrix[0].size() == 0)
      return 0;
  int rows = matrix.size();
  int cols = matrix[0].size();
  // 1. 求出矩阵中每个元素右边连续 1 的个数（包含这个元素本身），存储在 right1Len 中
  vector<vector<int>> right1Len(rows, vector<int>(cols, 0));
  for(int i = 0; i < rows; ++i)
  {
      right1Len[i][cols - 1] = matrix[i][cols - 1] == '1' ? 1 :0;
      for(int j = cols - 2; j >= 0; --j)
          right1Len[i][j] = matrix[i][j] == '0' ? 0 : right1Len[i][j + 1] + 1;
  }
  int result = 0;
  // 2. 遍历 right1Len 矩阵的每一列
  for(int j = 0; j < cols; ++j)
  {
      // 2.1 单调栈，求出每个元素下边最近的比它小的元素下标，存储在 down 
      vector<int> down(rows, 0);
      stack<int> s;
      for(int i = rows - 1; i >= 0; --i)    // 从下往上便利
      {
          while(!s.empty() && right1Len[s.top()][j] >= right1Len[i][j])
              s.pop();
          down[i] = s.empty() ? rows : s.top();
          s.push(i);
      }
      // 2.2 单调栈，求出每个元素上边最近的比它小的元素下标，存储在 up
      vector<int> up(rows, 0);
      while(!s.empty())
          s.pop();
      for(int i = 0; i < rows; ++i)        // 从上往下遍历
      {
          while(!s.empty() && right1Len[s.top()][j] >= right1Len[i][j])
              s.pop();
          up[i] = s.empty() ? -1 : s.top();
          s.push(i);
      }
      // 2.3 以每个元素的值（右边连续 1 的个数）为高度，down[i] - up[i] - 1 作为宽度
      // 求得矩形面积，与最大矩形面积比较，更新最大矩形面积
      for(int i = 0; i < rows; ++i)
      {
          int height = right1Len[i][j];
          int width = down[i] - up[i] - 1;
          int curArea = height * width;
          // cout << "i = " << i << ", j = " << j << ": height = " << height << ", down[i] = " << down[i] << ", up[i] = " << up[i] << ", curArea = " << curArea << endl;
          result = max(result, curArea);
      }
  }
  return result;
}
};

复杂度分析：设矩阵行数为 m，列数为 n

时间复杂度：遍历矩阵中的一列，时间复杂度 O(n)。然后对每一列的每一个元素，用单调栈求其下方最近的比它小的位置，求其上方最近的比它小的位置，再分别以每个元素为高度求最大矩形面积，三个操作的时间复杂度都为 O(m)
空间复杂度 O(mn)：right1Len 矩阵的空间复杂度

执行结果：

执行结果：通过
执行用时：44 ms, 在所有 C++ 提交中击败了 53.31% 的用户
内存消耗：15.1 MB, 在所有 C++ 提交中击败了 28.38% 的用户