# 0221. 最大正方形
### 题目地址(221. 最大正方形)
### 题目描述
```
在一个由 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 讨论](https://leetcode.com/problems/maximal-square/discuss/61803/C%2B%2B-space-optimized-DP)看一下。
### 关键点解析
* DP
* 递归公式可以利用 dp\[i - 1]\[j]和 dp\[i]\[j -1]的计算结果，而不用重新计算
* 空间复杂度可以降低到 O(n), n 为列数
### 代码
代码支持：Python，JavaScript：
Python Code：
```python
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
res = 0
m = len(matrix)
if m == 0:
return 0
n = len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 if matrix[i - 1][j - 1] == "1" else 0
res = max(res, dp[i][j])
return res ** 2
```
JavaScript Code：
```js
/*
* @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;
};
```
***复杂度分析***
* 时间复杂度：$O(M \* N)$，其中 M 为行数，N 为列数。
* 空间复杂度：$O(M \* N)$，其中 M 为行数，N 为列数。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/221.maximal-square.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.