目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
在一個由 '0' 和 '1' 組成的二維矩陣內，找到只包含 '1' 的最大正方形，并回傳其面積，
示例 1：
輸入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
輸出：4
示例 2：
輸入：matrix = [["0","1"],["1","0"]]
輸出：1
示例 3：
輸入：matrix = [["0"]]
輸出：0
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]為'0'或'1'
2、思路
(動態規劃) O ( n m ) O(nm) O(nm)
狀態表示： f[i][j]表示所有以(i,j)為右下角的且只包含1的正方形的邊長最大值，
狀態計算：
對于每個位置 (i, j)，檢查在矩陣中該位置的值：
- 如果該位置的值是
0，則f[i, j] = 0，因為當前位置不可能在由1組成的正方形中， - 如果該位置的值是
1，則f[i, j]的值由其上方、左方和左上方的三個相鄰位置的狀態值決定，具體而言，當前位置的元素值等于三個相鄰位置的元素中的最小值加1，
狀態轉移方程： f[i,j]=min(f[i?1,j?1],f[i?1,j],f[i,j?1])+1
類似于 木桶的短板理論， 附近的最小邊長，才與(i,j)的最長邊長有關，
時間復雜度分析： O ( n m ) O(nm) O(nm)，其中 n n n和 m m m是矩陣的行數和列數，
3、c++代碼
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> f(n + 1, vector<int>(m + 1));
int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (matrix[i - 1][j - 1] == '1') {
f[i][j] = min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j - 1])) + 1;
res = max(res, f[i][j]);
}
return res * res;
}
};
4、java代碼
class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix.length == 0 || matrix[0].length == 0) return 0;
int n = matrix.length, m = matrix[0].length;
int[][] f = new int[n + 1][m + 1];
int res = 0;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
if(matrix[i - 1][j - 1] == '1')
{
f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1;
res = Math.max(res, f[i][j]);
}
return res * res;
}
}
原題鏈接： 221. 最大正方形
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/292714.html
標籤：java