leetcode 關(guān)于矩形相關(guān)的題目真的太多了干像，把這些思路總結(jié)一下

0X00 面積類

最大正方形面積

221. 最大正方形

dp[i][j] 表示以 (i, j) 結(jié)尾的最大正方形邊長(zhǎng)偏序，最后取最大的邊長(zhǎng)的平方：

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. 最大矩形

思路單調(diào)棧蚌本，需要牢記

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 個(gè)數(shù)類

統(tǒng)計(jì)正方形個(gè)數(shù)

1277. 統(tǒng)計(jì)全為 1 的正方形子矩陣

與上面 dp 做法一模一樣片仿，原因是：最大邊長(zhǎng)是 n 就會(huì)有 n 個(gè)正方形逞壁，所以把所有相加就是最后的答案

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

統(tǒng)計(jì)矩形個(gè)數(shù)

1504. 統(tǒng)計(jì)全 1 子矩形 的做法在岂，這個(gè)做法匆瓜，很好理解但是很難想到：

可以參考這個(gè)題解：https://leetcode-cn.com/problems/count-submatrices-with-all-ones/solution/bian-tong-ji-bian-ya-suo-xiang-xi-by-quantum-10/ 寫得很好赢笨。

思路的關(guān)鍵在于：固定高度，遍歷以這個(gè)高度出現(xiàn)的矩形的個(gè)數(shù)驮吱。

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