[LeetCode] Maximal Square

Love The Way You Lie 2021-12-03 07:15 98阅读 0赞

[**Maximal Square**][Maximal Square]

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
    1 0 1 1 1
    1 1 1 1 1
    1 0 0 1 0

Return 4.

枚举就OK了，时间复杂度为O(n^3)，276ms AC。

1 class Solution {
     2 public:
     3     int getArea(vector<int> &array, int k) {
     4         if (array.size() < k) return 0;
     5         int cnt = 0;
     6         for (int i = 0; i < array.size(); ++i) {
     7             if (array[i] != k) cnt = 0;
     8             else ++cnt;
     9             if (cnt == k) return k * k;
    10         }
    11         return 0;
    12     }
    13     int maximalSquare(vector<vector<char>>& matrix) {
    14         vector<int> array;
    15         int res = 0;
    16         for (int i = 0; i < matrix.size(); ++i) {
    17             array.assign(matrix[0].size(), 0);
    18             for (int j = i; j < matrix.size(); ++j) {
    19                 for (int k = 0; k < matrix[0].size(); ++k) if (matrix[j][k] == '1') ++array[k];
    20                 res = max(res, getArea(array, j-i+1));
    21             }
    22         }
    23         return res;
    24     }
    25 };

可以使用动态规划优化到O(n^2)，下面的代码12ms AC。构造一个新的矩阵dp，dp\[i\]\[j\]表示以点(i, j)为右下角的正方形的边长；状态转移方程：

dp\[i\]\[j\] = min(dp\[i-1\]\[j-1\], min(dp\[i-1\]\[j\], dp\[i\]\[j-1\])) + 1;

对于题目所给的例子就有：

1 0 1 0 0
    1 0 1 1 1
    1 1 1 1 1
    1 0 0 1 0

转化成：

1 0 1 0 0
    1 0 1 1 1
    1 1 1 2 1
    1 0 0 1 0

1 class Solution {
     2 public:
     3     int maximalSquare(vector<vector<char>>& matrix) {
     4         if (matrix.empty() || matrix[0].empty()) return 0;
     5         int M = matrix.size(), N = matrix[0].size(), res = 0;
     6         vector<vector<int>> dp(M, vector<int>(N, 0));
     7         for (int i = 0; i < M; ++i) if (matrix[i][0] == '1') {
     8             dp[i][0] = 1; res = 1;
     9         }
    10         for (int j = 0; j < N; ++j) if (matrix[0][j] == '1') {
    11             dp[0][j] = 1; res = 1;
    12         }
    13         for (int i = 1; i < M; ++i) {
    14             for (int j = 1; j < N; ++j) {
    15                 if (matrix[i][j] == '1') 
    16                     dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
    17                 res = max(res, dp[i][j]);
    18             }
    19         }
    20         return res * res;
    21     }
    22 };

转载于:https://www.cnblogs.com/easonliu/p/4548769.html

[Maximal Square]: https://leetcode.com/problems/maximal-square/