LeetCode 1504. 统计全 1 子矩形

Categories:

题目描述
思路分析
1. 解法一：逐行统计高度 + 单调栈（推荐）
相似题目

题目描述

✅ 1504. 统计全 1 子矩形

思路分析

解法一：逐行统计高度 + 单调栈（推荐）

核心思路：

对矩阵每一行，计算每列从当前行向上连续 1 的高度，转化为”柱状图”问题

对每一行的高度数组，利用单调栈求每根柱子向左可延伸的最大宽度（即以当前柱为高度上界时）

对高度为 h 的柱子，它能贡献的子矩形数为：min(h, left[i]) - min(h, left[i-1])（逐差分统计）

等价地：枚举每根柱子为右边界，统计以其为右边界且满足条件的全 1 子矩形数目

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为矩阵行数和列数

空间复杂度：O(n)，高度数组与单调栈

class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        // height[j] 表示第 j 列从当前行向上的连续 1 高度
        int[] height = new int[n];
        int ans = 0;

        for (int i = 0; i < m; i++) {
            // 更新高度数组
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    height[j] = 0;
                } else {
                    height[j]++;
                }
            }

            // 对当前行的高度数组，统计以每列为右边界的全 1 子矩形数
            ans += countSubmat(height, n);
        }

        return ans;
    }

    private int countSubmat(int[] height, int n) {
        int count = 0;

        // sum[j] 表示以第 j 列为右边界时，可新增的子矩形行数
        int[] sum = new int[n];

        // 单调递增栈，存储列索引
        Deque<Integer> stack = new ArrayDeque<>();

        for (int j = 0; j < n; j++) {
            // 维护单调递增栈，弹出比当前高度大的元素
            while (!stack.isEmpty() && height[stack.peek()] >= height[j]) {
                stack.pop();
            }

            if (stack.isEmpty()) {
                // 左侧无更矮的柱子，当前高度可以延伸到最左
                sum[j] = height[j] * (j + 1);
            } else {
                int left = stack.peek();
                // 左侧有更矮的柱子，贡献为当前高度部分 + 之前累计
                sum[j] = height[j] * (j - left) + sum[left];
            }

            stack.push(j);
            count += sum[j];
        }

        return count;
    }
}

func numSubmat(mat [][]int) int {
    m, n := len(mat), len(mat[0])

    // height[j] 表示第 j 列从当前行向上的连续 1 高度
    height := make([]int, n)
    ans := 0

    for i := 0; i < m; i++ {
        // 更新高度数组
        for j := 0; j < n; j++ {
            if mat[i][j] == 0 {
                height[j] = 0
            } else {
                height[j]++
            }
        }

        // 对当前行的高度数组，统计以每列为右边界的全 1 子矩形数
        ans += countSubmat(height, n)
    }

    return ans
}

func countSubmat(height []int, n int) int {
    count := 0

    // sum[j] 表示以第 j 列为右边界时，可新增的子矩形行数
    sum := make([]int, n)

    // 单调递增栈，存储列索引
    stack := []int{}

    for j := 0; j < n; j++ {
        // 维护单调递增栈，弹出比当前高度大的元素
        for len(stack) > 0 && height[stack[len(stack)-1]] >= height[j] {
            stack = stack[:len(stack)-1]
        }

        if len(stack) == 0 {
            // 左侧无更矮的柱子，当前高度可以延伸到最左
            sum[j] = height[j] * (j + 1)
        } else {
            left := stack[len(stack)-1]
            // 左侧有更矮的柱子，贡献为当前高度部分 + 之前累计
            sum[j] = height[j]*(j-left) + sum[left]
        }

        stack = append(stack, j)
        count += sum[j]
    }

    return count
}

相似题目

题目	难度	考察点
85. 最大矩形	困难	单调栈、动态规划
84. 柱状图中最大的矩形	困难	单调栈
221. 最大正方形	中等	动态规划
1277. 统计全为 1 的正方形子矩阵	中等	动态规划
764. 最大加号标志	中等	动态规划
2201. 统计可以提取的工件	中等	矩阵、模拟

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/45820008