1504. 统计全 1 子矩形

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

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

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

  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)的列表,然后从后向前取最小的高度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