LeetCode-221. Maximal Square

LeetCode-221. Maximal Square

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

Example:

Input: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0Output: 4

题解：

动态规划问题。

此题若是用dfs肯定超时，想到dp。每个dp[i][j]表示以ij为右下角的最大正方形边长，它的大小受限于它的左边，上边和左上方三个为右下角的最大正方形边长，为三者的最小值 + 1。

class Solution {public: int maximalSquare(vector>& matrix) { if (matrix.empty() == true) { return 0; } int n = matrix.size(), m = matrix[0].size(), res = 0; vector> dp(n + 1, vector(m + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (matrix[i - 1][j - 1] == '1') { dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; res = max(res, dp[i][j] * dp[i][j]); } } } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。