題目描述

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

題解

動態(tài)規(guī)劃

代碼

class Solution { public:int maximalSquare(vector<vector<char>>& matrix) {int m=matrix.size();if (!m) return {};int n=matrix[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1));int res=0;for (int i=1;i<=m;i++){for (int j=1;j<=n;j++){if (matrix[i-1][j-1]=='0') dp[i][j]=0;else{dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;}res=max(res,dp[i][j]);}}return res*res;} };

總結(jié)

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

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