leetcode：221. 最大正方形

题目

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

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

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

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

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

解答 & 代码

解法一：单调栈

思路同：
[困难] 85. 最大矩形

  1. class Solution {
  2. public:
  3.     int maximalSquare(vector<vector<char>>& matrix) {
  4.         if(matrix.size() == 0 || matrix[0].size() == 0)
  5.             return 0;
  6.         int rows = matrix.size();
  7.         int cols = matrix[0].size();
  9.         vector<vector<int>> right1Len(rows, vector<int>(cols, 0));
  10.         for(int i = 0; i < rows; ++i)
  11.         {
  12.             right1Len[i][cols - 1] = matrix[i][cols - 1] == '0' ? 0 : 1;
  13.             for(int j = cols - 2; j >= 0; --j)
  14.                 right1Len[i][j] = matrix[i][j] == '0' ? 0 : right1Len[i][j + 1] + 1; 
  15.         }
  17.         int result = 0;
  18.         for(int j = 0; j < cols; ++j)
  19.         {
  20.             vector<int> up(rows);
  21.             stack<int> s;
  22.             for(int i = 0; i < rows; ++i)
  23.             {
  24.                 while(!s.empty() && right1Len[s.top()][j] >= right1Len[i][j])
  25.                     s.pop();
  26.                 up[i] = s.empty() ? -1 : s.top();
  27.                 s.push(i);
  28.             }
  30.             vector<int> down(rows);
  31.             while(!s.empty())
  32.                 s.pop();
  33.             for(int i = rows - 1; i >= 0; --i)
  34.             {
  35.                 while(!s.empty() && right1Len[s.top()][j] >= right1Len[i][j])
  36.                     s.pop();
  37.                 down[i] = s.empty() ? rows : s.top();
  38.                 s.push(i);
  39.             }
  41.             for(int i = 0; i < rows; ++i)
  42.             {
  43.                 int height = right1Len[i][j];
  44.                 int width = down[i] - up[i] - 1;
  45.                 int edge = min(height, width);
  46.                 int curArea = edge * edge;
  47.                 // cout << "i = " << i << ", j = " << j << ": height = " << height << ", down[i] = " << down[i] << ", up[i] = " << up[i] << ", curArea = " << curArea << endl;
  48.                 result = max(result, curArea);
  49.             }
  50.         }
  51.         return result;
  52.     }
  53. };

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

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

执行结果：

  1. 执行结果：通过
  3. 执行用时：88 ms, 在所有 C++ 提交中击败了 10.02% 的用户
  4. 内存消耗：22.2 MB, 在所有 C++ 提交中击败了 5.04% 的用户

解法二：动态规划

[中等] 221. 最大正方形