专栏首页苦逼的码农详解 leetcode 221 题:最大正方形

详解 leetcode 221 题:最大正方形

学好算法没有捷径,最好的捷径就是多刷题,并且跳出舒适区,每道题都要寻找最优解,也不能老是做那些你自己比较擅长的题,不定期更新 Leetcode 的题,每道题都会给出多种解法以及最优解

题目描述

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

示例

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

解法一:暴力法

在一个二维矩形中,如果我们要确定一个矩阵,我们只需要知道确定它的左上角右下角就可以了,而正方形相当于边相等的矩阵。这道题暴力法还是比较好做,就是把矩阵中的每一个点,都充当左上角来遍历搜索一下。

例如我刚开始把(0,0)这个点当左上角,然后向右下角搜索

搜索的过程中,用一个变量来记录最大正方形的面积。接着用(0,1)作为左上角,不断着向右下角搜索

当然,(0,1)这个位置本身就是 0 ,所以是没有搜索的必要的,我这里只是做个演示。最终的代码如下(可以左右滑动代码,也可以看图片版代码,下同)

    public int maximalSquare(char[][] matrix) {
        // 如果矩阵长或宽少于1则直接返回0
        if(matrix.length < 1 || matrix[0].length < 1)
            return 0;

        int rows = matrix.length;
        int cols = matrix[0].length;
        // 记录最大边长
        int max = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 把(i,j)作为左上角向右下角搜索
                if (matrix[i][j] == '1') {
                    // 此时正方形的边长
                    int sqlen = 1;
                    boolean flag = true;//记录是否遇到0的位置
                    while (sqlen + i < rows && sqlen + j < cols && flag) {
                        for (int k = j; k <= sqlen + j; k++) {
                            if (matrix[i + sqlen][k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        for (int k = i; k <= sqlen + i; k++) {
                            if (matrix[k][j + sqlen] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag)
                            sqlen++;
                    }
                    if (max < sqlen) {
                        max = sqlen;
                    }
                }
            }
        }
        return max * max;
    }

图片版代码:

  • 时间复杂度:O((mn)^2)
  • 空间复杂度:O(1)

解法二:动态规划

对于动态规划,大部分情况下我们都会定义一个二维数组dp,然后定义dp[i][j] 的含义,接着推导 dp[i][j] 与 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 之间的关系。当然,也可以是推导 dp[i][j] 与 dp[i+1][j]、dp[i][j+1]、dp[i+1][j+1] 之间的关系,下面我们讲下用 dp 该怎么解这道题。

1、首先我们定义 dp[i][j] 含义为正方形以 dp[i][j] 作为右下角时的最大边长值

2、接着我们来推导他们的关系

显然,对于任意一点 dp[i][j],由于该点是正方形的右下角,所以该点的右边,下边,右下边都不用考虑,关心的是左边,上边,和左上边,也就是我们要推导 dp[i][j] 与 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] 之间的关系。他们有如下关系

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

这个关系其实也不算难推,毕竟不能有 0 存在,所以只能取交他们三个点的交集。你们可以画个图,可能就比较好理解了。

代码如下(可以左右滑动代码,也可以看图片版代码,下同):

    public int maximalSquare(char[][] matrix) {
        // 如果矩阵长或宽少于1则直接返回0
        if(matrix.length < 1 || matrix[0].length < 1)
            return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] dp = new int[rows + 1][cols + 1];
        int max = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1'){
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max * max;
    }

图片版

  • 时间复杂度:O(n*m)
  • 空间复杂度:O(n*m)

解法三:动态规划优化

用动态规划时,可以说 80% 都是用二维数组,但是 80% 也都可以优化成一维数组,这很容易理解,大家看这个公式

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

通过上面的公式我们可以知道,我们要算 dp[i][j] 的值时,只需要用到 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 三个值就可以了。也就是说,我们在算矩阵 dp 第 i 行的值时,只需要用第 (i - 1) 行的值,至于(i-2)的值根本就不需要用到

所以我们只需要用一个一维数组就可以了,然后每次算出第 i 行的值,就马上用一维数组 dp[0….n] 把这行值保存起来,供计算 i+1 行时使用。

如下图

new_dp[i] 相当于二维矩阵的 dp[i][j]

dp[i] 相当于 dp[i-1][j]

dp[i-1] 相当于 dp[i-1][j]

pre 相当于 dp[i-1][j-1]。

然后用一维矩阵的话,我们每次计算出 new_dp[i] 后,就马上用 new_dp[i] 覆盖 dp[i] 的值,并且还要用一个变量 pre 来保存dp[i-1][j-1]的值。

好吧,估计你也给我绕晕了,如果不大理解,强烈建议画图模拟一下

最终代码如下(可以左右滑动代码,也可以看图片版代码,下同)

    public int maximalSquare(char[][] matrix) {
        if(matrix.length < 1 || matrix[0].length < 1)
            return 0;

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] dp = new int[cols + 1];
        int max = 0, prev = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
                    max = Math.max(max, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return max * max;
    }

图片版

  • 时间复杂度:O(n*m)
  • 空间复杂度:O(n)

额外话

动态规划是一个比较难的算法思想,特别是对于初学者,遇到动态规划的题基本凉,我刚开始也被搞过,后来能看懂关于动态规划的答案,但是自己写不出,一气之下做了几十道动态规划的题,发现做来做去套路都差不多,于是总结出了自己的一个套路模板,从此 80% 的动态规划题都会做。所以呢,后面找个时间我得写一写我的经验,这个经验适合看得懂动态规划,但又不知道怎么下手的人,不过写这篇文章估计需要挺长时间,所以几时写还没确定,,,,大家也可以学我,直接做 50 道动态规划的题,准稳。

本文分享自微信公众号 - 苦逼的码农(di201805),作者:帅地

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 告别动态规划,连刷40道动规算法题,我总结了动规的套路

    动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答...

    帅地
  • 动态规划该如何优化?我总结了这些套路,以后优化就是分分钟

    前两天写一篇长达 8000 字的关于动态规划的文章告别动态规划,连刷40道动规算法题,我总结了动规的套路

    帅地
  • 经典动态规划:高楼扔鸡蛋(进阶篇)

    我们在 上篇 聊了高楼扔鸡蛋问题:经典算法题:高楼扔鸡蛋 讲了一种效率不是很高,但是较为容易理解的动态规划解法。后台很多读者问如何更高效地解决这个问题,今天就谈...

    帅地
  • LeetCode-Longest Palindromic Subsequence

    这是LeetCode的第516道题目:516. Longest Palindromic Subsequence。

    卡尔曼和玻尔兹曼谁曼
  • LeetCode 516. 最长回文子序列(动态规划)

    Michael阿明
  • LintCode 最长公共子序列题目分析代码

    典型的动态规划问题 dp[i][[j]:表示前i个和前j个字符最大LCS 当A[i] = B[i]的时候: 那么显然dp[i][j] = dp[i-1][...

    desperate633
  • 画解算法:70. 爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    灵魂画师牧码
  • Leetcode 516. 最长回文子序列

    输入:"bbbab" 输出:4 解释: 一个可能的最长回文子序列为 "bbbb"。

    zhipingChen
  • 动态规划一篇就够了 全网第二详细, 逐步理解, 万字总结

    动态规划,一直以来听着就是一种很高深莫测的算法思想。尤其是上学时候算法的第一堂课,老师巴拉巴拉列了一大堆的算法核心思想,贪心、回溯、动态规划... ...,开始...

    Johngo
  • Leetcode 32 Longest Valid Parentheses DP好题

    Given a string containing just the characters '(' and ')', find the length of ...

    triplebee

扫码关注云+社区

领取腾讯云代金券