矩形相关思路总结

leetcode 关于矩形相关的题目真的太多了，把这些思路总结一下

0X00 面积类

最大正方形面积

221. 最大正方形

dp[i][j] 表示以 (i, j) 结尾的最大正方形边长，最后取最大的边长的平方：

class Solution:
    def maximalSquare(self, mat: List[List[int]]) -> int:
        if not len(mat): return 0
        m, n = len(mat), len(mat[0])
        dp = [[0] * (1+n) for _ in range(1+m)]
        ans = 0
        for i in range(1, 1+m):
            for j in range(1, 1+n):
                v = mat[i-1][j-1]
                if v == "0": continue
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                ans = max(ans, dp[i][j]) 
        
        return ans * ans

最大矩形面积

85. 最大矩形

思路单调栈，需要牢记

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not len(matrix): return 0
        m, n = len(matrix), len(matrix[0])
        def helper(hs):
            s, res = [-1], 0
            for i in range(n):
                h = hs[i]
                while s[-1] != -1 and hs[s[-1]] >= h:
                    th = hs[s.pop()]
                    res = max(res, th * (i - s[-1] - 1))
                s.append(i)
            
            while s[-1] != -1:
                th = hs[s.pop()]
                res = max(res, th * (n - s[-1] - 1))
            return res

        hs = [0 if matrix[0][i] == "0" else 1 for i in range(n)]
        s = helper(hs)
        for i in range(1, m):
            for j in range(n):
                if matrix[i][j] == "0": hs[j] = 0
                else: hs[j] += 1
            s = max(s, helper(hs))
        
        return s

0X01 个数类

统计正方形个数

1277. 统计全为 1 的正方形子矩阵

与上面 dp 做法一模一样，原因是：最大边长是 n 就会有 n 个正方形，所以把所有相加就是最后的答案

class Solution:
    def countSquares(self, mat: List[List[int]]) -> int:
        if not len(mat): return 0
        m, n = len(mat), len(mat[0])
        dp = [[0] * (1+n) for _ in range(1+m)]
        ans = 0
        for i in range(1, 1+m):
            for j in range(1, 1+n):
                v = mat[i-1][j-1]
                if v == 0: continue
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                ans += dp[i][j]
        
        return ans

统计矩形个数

1504. 统计全 1 子矩形 的做法，这个做法，很好理解但是很难想到：

可以参考这个题解：https://leetcode-cn.com/problems/count-submatrices-with-all-ones/solution/bian-tong-ji-bian-ya-suo-xiang-xi-by-quantum-10/ 写得很好。

思路的关键在于：固定高度，遍历以这个高度出现的矩形的个数。

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        ans = 0

        for i in range(m):
            for j in range(i, m):                
                now = 0
                for k in range(n):
                    if mat[j][k] == 0: now = 0
                    else: now = 1 if k == 0 or mat[j][k-1] == 0 else now + 1
                    ans += now
            for j in range(m-1, i, -1):
                for k in range(n):
                    mat[j][k] &= mat[j-1][k]

        return ans