221. Maximal Square
給定一個由0和1組成的m x n二進制矩陣，找出只包含1的最大正方形並返回其面積。
範例：
輸入:
matrix = [["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]
輸出:
輸出:
4
Python
from typing import List
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_side = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if matrix[i - 1][j - 1] == '1':
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_side
19.54MB, 519ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
int max_side = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
max_side = max(max_side, dp[i][j]);
}
}
}
return max_side * max_side;
}
};
24.88MB, 65ms
Javascript
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalSquare = function(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
return 0;
}
let m = matrix.length;
let n = matrix[0].length;
let dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0));
let maxSide = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] === '1') {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
};
56.02MB, 86ms
