LeetCode 1504. 统计全 1 子矩形

2021-09-04 HGNULB 约 5 分钟

文章信息 6 个分类 · 5 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 字节

标签

数组 动态规划 栈 矩阵 单调栈

题目描述

✅ 1504. 统计全 1 子矩形

题意分析

给定零一矩阵，统计有多少个非空子矩形内部全部为一。矩形必须使用连续行和连续列，每一组上下左右边界都单独计数。

目标是所有合法矩形的数量，不是最大面积，也不只统计正方形。不同大小或位置即使重叠，也分别算答案。

解法：逐行高度 + 单调栈计数

核心思路

[!blue]

枚举当前行作为矩形底边，用 heights[col] 表示这一列从当前行向上连续一的高度：当前格为一则加一，为零则清零。固定一段连续列后，矩形能向上延伸的最大高度是这些柱子的最小值，选择高度一到该最小值，各对应一个不同顶边。

因此，固定底边后需要求所有连续列区间的最小高度之和。令 ending[right] 表示以当前列为右端的所有区间最小值之和，也就是同时固定底边和右边界的矩形数。

维护高度严格递增的下标栈，弹出所有不低于当前高度的位置，留下最近的严格更矮位置 previous。把左端点分为两类：位于它右边的 right - previous 个起点，其区间高度都不低于当前柱，最小值就是当前高度，贡献 heights[right] * (right - previous)。

左端点不超过 previous 时，原区间到 previous 的最小高度不超过这根更矮柱，而新接上的柱全部更高，所以最小值完全不变。这部分贡献正好是已经计算的 ending[previous]。两类相加，就得到当前状态。

若不存在更矮位置，令 previous = -1，全部 right + 1 个起点都属于第一类，复用部分视为零。当前高度为零时，自然得到零贡献，不会把经过零的区域计入。

每行重新建立栈，从左到右覆盖 ending；所有被引用的前驱都在本行已经算好。每个矩形有唯一底边与右边界，将所有状态相加便不重不漏。

解题步骤

1. 初始化每列连续高度、当前行贡献数组和下标栈。
2. 处理新一行，遇一增加高度，遇零清空高度。
3. 重置栈，从左到右枚举矩形右边界。
4. 弹出不更矮的栈顶，找到最近严格更矮位置或使用 -1。
5. 用前驱贡献加上当前高度乘新增起点数量，得到 ending[right]。
6. 将贡献加入总答案，再把当前下标入栈；继续下一行。

代码实现

class Solution {
    public int numSubmat(int[][] mat) {
        int columns = mat[0].length;
        int[] heights = new int[columns];
        int[] ending = new int[columns];
        int[] stack = new int[columns];
        int answer = 0;

        for (int[] row : mat) {
            for (int col = 0; col < columns; col++) {
                heights[col] = row[col] == 0 ? 0 : heights[col] + 1;
            }

            // 当前行重新建立单调关系，不能复用上一行的栈。
            int top = -1;

            for (int right = 0; right < columns; right++) {
                // 弹出不更矮的位置，留下最近的严格更矮下标。
                while (top >= 0 && heights[stack[top]] >= heights[right]) {
                    top--;
                }

                int previous = top >= 0 ? stack[top] : -1;

                // 右侧新区间贡献当前高度；更左区间复用本行前驱贡献。
                ending[right] =
                        (previous >= 0 ? ending[previous] : 0)
                                + heights[right] * (right - previous);
                answer += ending[right];
                stack[++top] = right;
            }
        }

        return answer;
    }
}

func numSubmat(mat [][]int) int {
    columns := len(mat[0])
    heights := make([]int, columns)
    ending := make([]int, columns)
    stack := make([]int, columns)
    answer := 0

    for _, row := range mat {
        for col := 0; col < columns; col++ {
            if row[col] == 0 {
                heights[col] = 0
            } else {
                heights[col]++
            }
        }

        // 当前行重新建立单调关系，不能复用上一行的栈。
        top := -1
        for right := 0; right < columns; right++ {
            // 弹出不更矮的位置，留下最近的严格更矮下标。
            for top >= 0 && heights[stack[top]] >= heights[right] {
                top--
            }
            previous := -1
            if top >= 0 {
                previous = stack[top]
            }
            // 右侧新区间贡献当前高度；更左区间复用本行前驱贡献。
            ending[right] = heights[right] * (right - previous)
            if previous >= 0 {
                ending[right] += ending[previous]
            }
            answer += ending[right]
            top++
            stack[top] = right
        }
    }
    return answer
}

复杂度分析

• 时间复杂度：$O(mn)$，每行更新高度为线性，各列下标至多入栈、出栈一次。
• 空间复杂度：$O(n)$，保存高度、当前行贡献和栈，均按列数分配。

关键点总结

[!green]

• 柱状图的区间最小高度，等于固定底边与左右边界后可选的顶边数量。
• 最近更矮位置把左端点分成新增贡献与不变贡献两部分。
• 前驱的旧区间接上更高柱，最小值不变，因而能复用其整段贡献。
• 按唯一底边和右边界分类累加，覆盖全部矩形且不重复。

易错点总结

[!yellow]

• 遇零不清高度，会把被零隔开的竖直一段错误地连起来。
• 只累加各列高度，得到的只是单列矩形，漏掉跨列矩形。
• 复用上一行栈会使用已经过时的高度关系，栈每行必须重建。
• 新增起点数量为 right - previous，不能再加一，previous 对应的起点已包含在复用部分。
• ending 可覆盖复用，但只能引用当前行已计算的更左位置，不能使用上一行残留值。

相似题目

题目	难度	关联与区别
907. 子数组的最小值之和	中等	逐列累计以当前行为底的连续1高度；该行底部全1矩形数等于这些柱高的子数组最小值之和。

转载与许可

作者 HGNULB

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

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！