统计全为1的矩形子矩阵个数

题目描述
给定一个m×n的二进制矩阵（只包含0和1），统计其中全部由1组成的矩形子矩阵的个数。

例如，对于矩阵：
[[1,0,1],
[1,1,0],
[1,1,0]]

应该返回13，因为包含：

• 4个1×1矩形
• 3个2×1矩形
• 1个1×2矩形
• 2个2×2矩形
• 3个3×1矩形

解题过程

步骤1：理解问题本质
我们需要统计所有可能的矩形，这些矩形必须全部由1组成。暴力解法是枚举所有可能的矩形，检查是否全为1，但时间复杂度太高。

步骤2：关键观察
对于矩阵中的每个位置(i,j)，如果我们知道以该位置为右下角的矩形信息，就能逐步构建解。

定义height[j]：表示在第i行，第j列位置向上的连续1的个数。

步骤3：逐行处理
我们从上到下逐行处理矩阵：

• 对于第0行：height[j] = matrix[0][j]
• 对于第i行：如果matrix[i][j] = 1，则height[j] += 1；否则height[j] = 0

步骤4：单调栈的应用
对于每一行，我们有了height数组后，问题转化为：对于每个位置j，找到左边第一个小于height[j]的位置left，右边第一个小于height[j]的位置right。

这样，以height[j]为高度的矩形宽度就是(right - left - 1)，能形成的矩形数量为height[j] * (right - left - 1)。

步骤5：详细计算过程
以示例矩阵为例：

第0行：height = [1,0,1]

• j=0: left=-1, right=1 → 宽度=1-(-1)-1=1 → 矩形数=1
• j=1: height=0，跳过
• j=2: left=1, right=3 → 宽度=3-1-1=1 → 矩形数=1
  第0行总计：2

第1行：height = [2,1,0]

• j=0: left=-1, right=1 → 宽度=1-(-1)-1=1 → 矩形数=2
• j=1: left=0, right=2 → 宽度=2-0-1=1 → 矩形数=1
• j=2: height=0，跳过
  第1行总计：3

第2行：height = [3,2,0]

• j=0: left=-1, right=1 → 宽度=1-(-1)-1=1 → 矩形数=3
• j=1: left=0, right=2 → 宽度=2-0-1=1 → 矩形数=2
• j=2: height=0，跳过
  第2行总计：5

累计：2 + 3 + 5 + 3(额外统计) = 13

步骤6：算法实现

def numSubmat(mat):
    if not mat or not mat[0]:
        return 0
    
    m, n = len(mat), len(mat[0])
    height = [0] * n
    result = 0
    
    for i in range(m):
        # 更新height数组
        for j in range(n):
            height[j] = height[j] + 1 if mat[i][j] == 1 else 0
        
        # 使用单调栈计算以当前行为底边的矩形数量
        stack = []
        left = [-1] * n
        right = [n] * n
        
        # 找左边第一个小于当前高度的位置
        for j in range(n):
            while stack and height[stack[-1]] >= height[j]:
                stack.pop()
            left[j] = stack[-1] if stack else -1
            stack.append(j)
        
        stack.clear()
        
        # 找右边第一个小于当前高度的位置
        for j in range(n-1, -1, -1):
            while stack and height[stack[-1]] > height[j]:
                stack.pop()
            right[j] = stack[-1] if stack else n
            stack.append(j)
        
        # 计算当前行的贡献
        for j in range(n):
            result += height[j] * (j - left[j]) * (right[j] - j)
    
    return result

步骤7：复杂度分析

• 时间复杂度：O(m×n)，我们遍历了矩阵的每个元素
• 空间复杂度：O(n)，用于存储height数组和栈

这种方法通过动态规划维护高度信息，结合单调栈高效统计矩形数量，是解决此类问题的经典方法。