题目地址
https://leetcode.com/problems/maximal-square/
题目描述
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
思路
符合直觉的做法是暴力求解处所有的正方形,逐一计算面积,然后记录最大的。这种时间复杂度很高。
我们考虑使用动态规划,我们使用dp[i][j]表示以matrix[i][j]为右下角的顶点的可以组成的最大正方形的边长。
那么我们只需要计算所有的i,j组合,然后求出最大值即可。
我们来看下dp[i][j] 怎么推导。 首先我们要看matrix[i][j], 如果matrix[i][j]等于0,那么就不用看了,直接等于0。
如果matrix[i][j]等于1,那么我们将matrix[[i][j]分别往上和往左进行延伸,直到碰到一个0为止。
如图 dp[3][3] 的计算。 matrix[3][3]等于1,我们分别往上和往左进行延伸,直到碰到一个0为止,上面长度为1,左边为3。
dp[2][2]等于1(之前已经计算好了),那么其实这里的瓶颈在于三者的最小值, 即Min(1, 1, 3)
, 也就是1
。 那么dp[3][3] 就等于
Min(1, 1, 3) + 1
。
dp[i - 1][j - 1]我们直接拿到,关键是往上和往左进行延伸
, 最直观的做法是我们内层加一个循环去做就好了。
但是我们仔细观察一下,其实我们根本不需要这样算。 我们可以直接用dp[i - 1][j]和dp[i][j -1]。
具体就是Min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
。
事实上,这道题还有空间复杂度O(N)的解法,其中N指的是列数。
大家可以去这个leetcode讨论看一下。
关键点解析
- DP
- 递归公式可以利用dp[i - 1][j]和dp[i][j -1]的计算结果,而不用重新计算
- 空间复杂度可以降低到O(n), n为列数
代码
/* * @lc app=leetcode id=221 lang=javascript * * [221] Maximal Square */ /** * @param {character[][]} matrix * @return {number} */ var maximalSquare = function(matrix) { if (matrix.length === 0) return 0; const dp = []; const rows = matrix.length; const cols = matrix[0].length; let max = Number.MIN_VALUE; for (let i = 0; i < rows + 1; i++) { if (i === 0) { dp[i] = Array(cols + 1).fill(0); } else { dp[i] = [0]; } } for (let i = 1; i < rows + 1; i++) { for (let j = 1; j < cols + 1; j++) { if (matrix[i - 1][j - 1] === "1") { dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1; max = Math.max(max, dp[i][j]); } else { dp[i][j] = 0; } } } return max * max; };LeetCode题解计算机为什么是基于二进制的?
可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈
LeetCode题解10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。要求用程序模拟十万次,暴力求出该概率来自:字节跳动 算法工程师一面的第一题 (3月30日,60分钟,牛客网视频面)https://www.nowcoder.com/discuss/395924
LeetCode题解微信红包微信红包 如何分配 让每个人在数学期望上是一样的?在概率论和统计学中,数学期望(mean)(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。 它反映随机变量平均取值的大小。 需要注意的是,期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。 期望值是该变量输出值的平均数。