221. Maximal Square
Tags:
Medium
Skills:
Matrix
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Approach
Bài tập này có thể sử dụng DP, một cách tiếp cận hiệu quả để tìm diện tích hình vuông lớn nhất chỉ chứa các chỉ số 1 trong ma trận nhị phân
dp[i][j] = min(dp[i -1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
Time and space complexity
Solution
1function maximalSquare(matrix: string[][]): number {
2 const rows = matrix.length;
3 const cols = matrix[0].length;
4
5 const dp: number[][] = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0))
6 let max_side = 0;
7
8 for (let i = 1; i <= rows; i++) {
9 for (let j = 1; j <= cols; j++) {
10 if (matrix[i - 1][j - 1] === '1') {
11 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
12 max_side = Math.max(max_side, dp[i][j]);
13 }
14 }
15 }
16
17 return max_side * max_side
18};Solution - Optimize SC: O(n)
1function maximalSquare(matrix: string[][]): number {
2 const rows = matrix.length;
3 const cols = matrix[0].length;
4
5 // const dp: number[][] = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0))
6 const dp: number[] = Array(cols + 1).fill(0);
7 let max_side = 0;
8 let prev = 0;
9
10 for (let i = 1; i <= rows; i++) {
11 for (let j = 1; j <= cols; j++) {
12 let temp = dp[j];
13 if (matrix[i - 1][j - 1] === '1') {
14 dp[j] = Math.min(dp[j - 1], dp[j], prev) + 1;
15 max_side = Math.max(max_side, dp[j])
16 } else {
17 dp[j] = 0;
18 }
19 prev = temp;
20 }
21 }
22
23 return max_side * max_side
24};Điều kiện if(maxtrix[i - 1][j - 1]) === '1' chỉ kiếm tra xem ô hiện tại trong ma trận gốc có phải là ‘1’ không, tức là ô này có thể là một phần của hình vuông toàn ‘1’ hay không. Nếu ‘0’ , chắc chắn không thể mở rộng hình vuông tại đây nên ta bỏ qua cập nhật dp cho ô này
Tuy nhiên, khi cập nhật giá trị DP, ta phải xét cả ba ô lân cận: phía trên (dp[i - 1][j]), bên trái (dp[i][j - 1]), và đường chéo trên-trái (dp[i - 1][j - 1]). Công thức:
dp[i][j]=min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1])+1
là để đảm bảo rằng tại vị trí (i, j) có thể tạo thành một hình vuông lớn hơn nếu và chỉ nếu cả ba ô lân cận cũng đều là phần cuối của các hình vuông toàn '1' có cạnh ít nhất là kk. Khi đó, cạnh hình vuông mới tại (i, j) sẽ là k+1k+1
Tóm lại:
matrix[i - 1][j - 1] === '1' chỉ kiểm tra xem ô hiện tại có phải là '1' hay không.min của cả ba ô lân cận (trên, trái, chéo trên-trái) là để đảm bảo hình vuông mở rộng hợp lệ về cả ba hướng, không chỉ đường chéo