221.maximal-square.md

题目地址(221. 最大正方形)

https://leetcode-cn.com/problems/maximal-square/

题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 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 为列数

代码

代码支持：Python，JavaScript：

Python Code：

classSolution: defmaximalSquare(self, matrix: List[List[str]]) ->int: res=0m=len(matrix) ifm==0: return0n=len(matrix[0]) dp= [[0] * (n+1) for_inrange(m+1)] foriinrange(1, m+1): forjinrange(1, n+1): dp[i][j] =min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) +1ifmatrix[i-1][j-1] =="1"else0res=max(res, dp[i][j]) returnres**2

JavaScript Code：

/* * @lc app=leetcode id=221 lang=javascript * * [221] Maximal Square *//** * @param {character[][]} matrix * @return {number} */varmaximalSquare=function(matrix){if(matrix.length===0)return0;constdp=[];constrows=matrix.length;constcols=matrix[0].length;letmax=Number.MIN_VALUE;for(leti=0;i<rows+1;i++){if(i===0){dp[i]=Array(cols+1).fill(0);}else{dp[i]=[0];}}for(leti=1;i<rows+1;i++){for(letj=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;}}}returnmax*max;};

复杂度分析

• 时间复杂度：$O(M * N)$，其中 M 为行数，N 为列数。
• 空间复杂度：$O(M * N)$，其中 M 为行数，N 为列数。