【动态规划】221. 最大正方形

2024-01-01 14:27:59

221. 最大正方形

解题思路

  • 参考题解:https://leetcode.cn/problems/maximal-square/solutions/44586/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/?show=1
  • 主要思想:选择左边 上面 左上方 最小的值,dp[i+1][j+1]代表以第i行 第j列为右下角的正方形的最大边长
class Solution {
    public int maximalSquare(char[][] matrix) {
        // BASE CASE 没有元素的情况
        if(matrix == null || matrix.length < 1 || matrix[0].length < 1){
            return 0;
        }

        int height = matrix.length;
        int width = matrix[0].length;
        int maxSide = 0;


        // 新增一行 一列  全部都是0
        int[][] dp = new int[height + 1][width + 1];

        // dp[i+1][j + 1]表示 以第i行 第j列为右下角的正方形的最大边长
        // dp[1][1] 表示以(0,0)为右下角边界的正方形的最大边长


        for(int row = 0; row < height; row++){
            for(int col = 0; col < width; col++){
                if(matrix[row][col] == '1'){
                    dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col],dp[row][col+1]),dp[row][col]) + 1;
                    maxSide = Math.max(maxSide,dp[row+1][col+1]);
                }
            }
        }

        return maxSide * maxSide;
    }
}

文章来源:https://blog.csdn.net/qq_44653420/article/details/135324644
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。