LeetCode-221. 最大正方形

墨蓝 2022-01-27 01:23 345阅读 0赞

221. 最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

  1. 1 0 1 0 0
  2. 1 0 1 1 1
  3. 1 1 1 1 1
  4. 1 0 0 1 0

输出: 4

动态规划

状态转移方程:dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j])
dp[i][j]表示以(i,j)为右下角所能构成的最大正方形的边长。

  1. class Solution { 
  2. public:
  3.     int maximalSquare(vector<vector<char>>& matrix) { 
  4.         int len = matrix.size();
  5.         if(len == 0) return 0;
  6.         int width = matrix[0].size();
  7.         vector<vector<int>> dp(len + 1,vector<int>(width + 1,0));
  8.         int ans = 0;
  9.         for(int i = 1;i <= len;i++) { 
  10.             for(int j = 1;j <= width;j++) { 
  11.                 if(matrix[i - 1][j - 1] == '1') { 
  12.                     dp[i][j] = min(dp[i - 1][j - 1],min(dp[i - 1][j],dp[i][j - 1])) + 1;
  13.                     ans = max(ans,dp[i][j]);
  14.                 }
  15.             }
  16.         }   
  17.         return ans*ans;
  18.     }
  19. };

发表评论

表情：
评论列表 （有 0 条评论，345人围观）

还没有评论，来说两句吧...

相关阅读

    相关 221. 最大正方形

    打卡!!!每日一题 今天继续给大家分享一道动态规划类型的题目，不过该题目的状态转移方程比较难以理解，我会详细的给大家分析一下 题目描述： > 在一个由 ‘0’ 和 ‘1’

    川长思鸟来川长思鸟来/ 0 赞/ 137 阅读

    相关 221. 最大正方形

    在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 输入:  1 0 1 0 0 1 0 1 1 1 1 1 1 1 1

    小灰灰小灰灰/ 0 赞/ 113 阅读

    相关 Leetcode 221 最大正方形(DP)

    题目重述 在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。 示例 1： ![在这里插入图片描述][watermark

    墨蓝墨蓝/ 0 赞/ 262 阅读