文章目錄

• • 1. 題目信息
  • 2. 解題

1. 題目信息

在一個由 0 和 1 組成的二維矩陣內，找到只包含 1 的最大正方形，并返回其面積。

示例:

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/maximal-square
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：LeetCode 85. 最大矩形（DP，難）

class Solution { public:int maximalSquare(vector<vector<char>>& matrix) {if(matrix.empty())return 0;int i, j, n, incr, maxEdgeLen = 0;int r = matrix.size(), c = matrix[0].size();int dp[r][c];//以右下角為結束的最大正方形邊長for(i = 0; i < r; ++i)for(j = 0; j < c; ++j){dp[i][j] = 0;//初始化為0}for(i = 0; i < c; ++i)//第一行填表{if(matrix[0][i] == '1')dp[0][i] = 1;}for(i = 1; i < r; ++i)//第一列填表{if(matrix[i][0] == '1')dp[i][0] = 1;}for(i = 1; i < r; ++i)for(j = 1; j < c; ++j){if(matrix[i][j] == '0')dp[i][j] = 0;else//matrix[i][j] == '1'{n = dp[i-1][j-1];incr = 0;while(n--){incr++;//記錄同時為1的次數if(matrix[i-incr][j] == '1' && matrix[i][j-incr] == '1'){continue;//往左和往上同時判斷都為1嗎？}else//有中斷則跳出{incr--;break;}}dp[i][j] = 1+incr;}}for(i = 0; i < r; ++i)for(j = 0; j < c; ++j){if(dp[i][j] > maxEdgeLen)//尋找最大邊長maxEdgeLen = dp[i][j];}return maxEdgeLen*maxEdgeLen;//返回最大面積} };

• 又發現以（i，j）為右下角的最大正方形邊長 dp[i][j] 就是 min（dp[i-1][j], dp[i][j-1], dp[i-1][j-1]）(i,j 位置左上角3個點的最大邊長中的最小者)
  對以上結論，可以自己嘗試將1變成0, 0變成1，自己畫個圖試下。

對上面程序進行小的修改

class Solution { public:int maximalSquare(vector<vector<char>>& matrix) {if(matrix.empty())return 0;int i, j, n, incr, maxlen = 0;int r = matrix.size(), c = matrix[0].size();int dp[r][c];//以右下角為結束的最大正方形邊長memset(dp,0,sizeof(dp));for(i = 0; i < c; ++i)//第一行填表{if(matrix[0][i] == '1')dp[0][i] = 1,maxlen = 1;}for(i = 1; i < r; ++i)//第一列填表{if(matrix[i][0] == '1')dp[i][0] = 1,maxlen = 1;}for(i = 1; i < r; ++i){for(j = 1; j < c; ++j){if(matrix[i][j]=='1'){dp[i][j] = 1+min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]));maxlen = max(maxlen, dp[i][j]);}}}return maxlen*maxlen;} };

總結

以上是生活随笔為你收集整理的LeetCode 221. 最大正方形（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。