题目

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例：
[中等] 221. 最大正方形 - 图1

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

[中等] 221. 最大正方形 - 图2

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

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

解答 & 代码

解法一：单调栈

参考：
[困难] 85. 最大矩形

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if(rows == 0)
            return 0;
        int cols = matrix[0].size();
        if(cols == 0)
            return 0;

        // 1. 先求出矩阵 matrix 中每个元素左边连续 1 的个数（包含这个元素本身），存储在矩阵 left 中
        vector<vector<int>> left(rows, vector<int>(cols, 0));
        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;
        }

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

            // 2.2 以该列每行元素（柱子高度） & 该高度对应的宽度的较小值为正方形的边，
            // 计算正方形面积，如果大于最大面积，就更新最大面积的值
            for(int i = 0; i < rows; ++i)
            {
                int squareLen = min(left[i][j], down[i] - up[i] - 1);
                int area = squareLen * squareLen;
                if(area > maxArea)
                    maxArea = area;
            }
        }

        return maxArea;
    }
};

执行结果：

执行结果：通过

执行用时：68 ms, 在所有 C++ 提交中击败了 7.38% 的用户
内存消耗：20.6 MB, 在所有 C++ 提交中击败了 5.28% 的用户

解法二：动态规划

动态规划：

设置数组 dp，dp[i][j] 代表以第 i 行第 j 列这个格子为右下角的最大正方形的边长

状态转移方程：证明见 https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/solution/tong-ji-quan-wei-1-de-zheng-fang-xing-zi-ju-zhen-2/

dp[i][j]     = matrix[i][j]                                                                        , if i == 0 or j == 0（初始化）
                  = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1        , else if matrix[i][j] == '1'
        = 0                                                                                                , else if matrix[i][j] == '0'

初始化：第 0 行和第 0 列的元素 dp[i][j] 取决于 matrix[i][j]

class Solution {
public:
  int maximalSquare(vector<vector<char>>& matrix) {
      int rows = matrix.size();
      if(rows == 0)
          return 0;
      int cols = matrix[0].size();
      if(cols == 0)
          return 0;

      int maxSquareLen = 0;    // 最大正方形的边长

      // 动态规划，dp[i][j] 代表以第 i 行第 j 列这个格子为右下角的最大正方形的边长
      vector<vector<int>> dp(rows, vector<int>(cols, 0));
      for(int i = 0; i < rows; ++i)
      {
          for(int j = 0;j < cols; ++j)
          {
              // 初始化
              if(i == 0 || j == 0)    
                  dp[i][j] = matrix[i][j] - '0';
              // 状态转移
              else if(matrix[i][j] == '1')
                  dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
              else 
                  dp[i][j] = 0;

              // 更新最大正方形的边长
              if(dp[i][j] > maxSquareLen)
                  maxSquareLen = dp[i][j];
          }
      }

      return maxSquareLen * maxSquareLen;
  }
};

``` 执行结果：通过

执行用时：24 ms, 在所有 C++ 提交中击败了 91.99% 的用户内存消耗：11.6 MB, 在所有 C++ 提交中击败了 47.56% 的用户 ```