LC 1504. 统计全 1 子矩形

https://leetcode-cn.com/problems/count-submatrices-with-all-ones/

我觉得大家对类似 求解一个矩阵的最大子矩阵 这样的问题肯定不会陌生，有个叫做Kadane的算法。其实这个算法本质思想不难，操作也很简单：

• 首先我们对行做个二重遍历 `for i in range(n) for j in range(i)`
• 然后我们会维护一个列的前缀和数组 `sums`, 其中 `sums[k]` 表示 `sum(Rect(i..j, k-1..k-1))`
• 然后在遍历 `k` 的时候，可以利用求解子序列最大和的算法，线性地得到最大值。
• 这样下来时间复杂度是O(n^2 * m), 空间复杂度是 O(m)
• 如果 n>>m 的话，那么可以对列做二重遍历。

我觉得这是求解子矩阵问题的一种套路，这种套路分为：

1. 对行做二重遍历，这样就是 O(n^2)
2. 对列做一定的bookkeeping, 然后利用这个信息求解答案，通常复杂度是 O(m)
3. 这样总的时间复杂度就是 O(n^2 * m)

这个套路在一定程度上也可以用在这题上（但是写着写着，我发现和这题解法还是有一定差别的）。这题的解决办法可以看下图

0 1 2 3 4
0       x
1   x   x
2   x x x
3   x x x
4   x x x
5 x x x x(here)

假设我们遍历到了(5, 4)这个元素，我们知道之前最大高度分别是 [1,5,4,6]，那么以(5,4)为最右下角元素的矩阵有：

• 宽度为1的话，有6个
• 宽度为2的话，有4个
• 宽度为3的话，只有4个（虽然列2上的高度为5）
• 宽度为4的话，有1个

所以这个算法是，对于每一列我们需要维护一个最大高度(连续为1)的列表，然后从后向前取最小的高度k，作为"如果宽度为x的话，那么有k个矩阵"

这个算法的时间复杂度是 O(n * m^2). 如果 n<<m 的话，那么其实也可以改为 O(n^2 * m). 代码如下：

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        hs = [0] * m
        ans = 0
        for i in range(n):
            for j in range(m):
                if mat[i][j] == 0:
                    hs[j] = 0
                    continue

                hs[j] += 1
                h = hs[j]
                for k in reversed(range(j+1)):
                    h = min(h, hs[k])
                    ans += h
                    if h == 0:
                        break
        return ans