看似一致的面积问题

这两道题看起来是比较类似的，都是求二维矩阵中的面积问题，但是两题的解题思路完全不一致。

第一道题可以使用使用二维dp数组表示构成最大正方形的最长边长，但是第二题不行，它边长是由长宽构成，如果使用动态规划，那么需要两个dp数组，一个代表最长宽，一个代表最长高。

如果用第二题dp代表最大矩形面积，这样又会没有递推关系。

但是关于矩形面积都有一个统一思路就是求，最长宽高，得到最长的宽高也就得到了最大矩形面积

221. 最大正方形——正方形最大面积

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

示例 1：

img

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

img

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 '0' 或 '1'

思路看注释

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        """
        dp数组含义：
        dp[i][j]代表着，i,j处所能构成最大正方形的最大边长
        递推公式：
            if matrix[i][j] == '1':
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
        初始化：
            第0行和第0列值为1需要进行初始化为1
        遍历顺序：
            从左到右，从上到下，正序
        """
        m = len(matrix)
        n = len(matrix[0])
        if m == n == 0:
            return 0

        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if matrix[i][0] == "1":
                dp[i][0] = 1
        for j in range(n):
            if matrix[0][j] == "1":
                dp[0][j] = 1

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == "1":
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
        # print(dp)
        return max([max(i) for i in dp]) ** 2

LCR 040. 最大矩形——最大矩形

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

**注意：**此题 matrix 输入格式为一维 01 字符串数组。

示例 1：

img

输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = ["0"]
输出：0

示例 4：

输入：matrix = ["1"]
输出：1

示例 5：

输入：matrix = ["00"]
输出：0

提示：

• rows == matrix.length
• cols == matrix[0].length
• 0 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'