1. 題目

在一個由 0 和 1 組成的二維矩陣內(nèi)，找到只包含 1 的最大正方形，并返回其面積。示例:輸入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0輸出: 4

2. 代碼

• 函數(shù)

vector<vector> dp(m+1, vector(n+1, 0)); 定義二維vector以及其初始化！！！

當測試用例是 [] 的時候，只有row的值， 沒有col的值

min 和 max只有兩個參數(shù)，第三個參數(shù)如果有的話為operation。 所以我們采用的是
min(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1])) 嵌套min

• 核心思想

我們了解到最大的正方形應該是從

DP[i][j]來記錄以點i，j為右下角的全1矩陣的最大邊長。 即DP[i][j]表示的是邊長大小！！！

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

class Solution { public:int maximalSquare(vector<vector<char>>& matrix) {int m = matrix.size();if(m==0) return 0; //防止測試用例是 []， 這個時候，只有所謂的行m， 不存在n。 int n = matrix[0].size();int maxSqr = 0;vector<vector<int>> dp(m+1, vector<int>(n+1, 0));for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) {if(matrix[i-1][j-1] == '1') { //只有當其左上角是1的時候才執(zhí)行下面的操作dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1])) + 1;maxSqr = max(dp[i][j], maxSqr);}}}return maxSqr * maxSqr;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode之最大正方形的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。