LeetCode LCR 040. 最大矩形

约 5 分钟
文章信息 5 个分类 6 个标签
分类
LeetCode 困难 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 动态规划 栈 LCR 矩阵 单调栈

题目描述

✅ LCR 040. 最大矩形

image-20260928235646484

image-20260928235646486

题意分析

输入是由 01 字符串组成的数组，每个字符串表示一行，求全部为 $1$ 的最大轴对齐矩形面积。本文接口为 Java String[]、Go []string，空矩阵或没有列时返回 $0$。

每个矩形都有确定的底边行。可以枚举底边，把这一行之上各列连续的 $1$ 压成柱高，将二维问题转成柱状图最大矩形。

解法：逐行转柱状图 + 单调栈

核心思路

[!blue]

用 heights[col] 保存当前行这一列向上连续的 $1$ 的数量。当前字符为 '1' 时在上一行高度上加一，为 '0' 时清零，因为以当前行为底的全一矩形不能跨过这个零。

固定当前行为底，选定一段连续列时，矩形高度至多是这些列高的最小值。反过来，柱状图中任意高度为 h 的合法矩形，都对应原矩阵中向上连续 h 行的全一矩形。因此本行的最大面积恰好等于当前柱状图的最大面积；遍历全部底边行，就不会漏掉全局答案。

对每行柱状图新建下标栈，保持栈底到栈顶高度单调不减。当前高度更矮时，连续弹出较高柱子。弹出高度为 height，新栈顶为 left（空栈取 -1），当前下标为 i，本次可计算的宽度就是 i - left - 1。

严格 > 弹栈会保留等高柱子，所以新栈顶有时只是同高度候选，不能把它一律看作严格更矮的左边界。较靠右的等高柱子先算较短区间，较靠左的最后覆盖完整宽度，最大面积仍会被计算。每行末尾使用虚拟高度 $0$，结算所有剩余正高度候选。

解题步骤

  1. 判空后创建全零列高数组，答案初始化为 $0$。
  2. 逐行更新所有列高：字符为 '1' 时加一，否则清零。
  3. 调用柱状图算法，用新栈处理本行高度，弹出时按 height * (i - left - 1) 更新面积。
  4. 处理末尾虚拟高度后，取本行结果与已有答案的最大值，再进入下一行。
  5. 返回所有行中的最大面积。全零矩阵的列高始终为零，结果自然为 $0$。

代码实现

class Solution {
    public int maximalRectangle(String[] matrix) {
        if (matrix.length == 0 || matrix[0].length() == 0) {
            return 0;
        }

        int[] heights = new int[matrix[0].length()];
        int ans = 0;

        for (String row : matrix) {
            for (int col = 0; col < row.length(); col++) {
                heights[col] = row.charAt(col) == '1' ? heights[col] + 1 : 0;
            }

            ans = Math.max(ans, largestRectangleArea(heights));
        }

        return ans;
    }

    private int largestRectangleArea(int[] heights) {
        int[] stack = new int[heights.length + 1];
        int top = -1;
        int ans = 0;

        for (int i = 0; i <= heights.length; i++) {
            int cur = i == heights.length ? 0 : heights[i];

            while (top >= 0 && heights[stack[top]] > cur) {
                // 当前柱子右侧第一个更矮位置已出现，可以结算栈顶高度。
                int height = heights[stack[top--]];
                int left = top >= 0 ? stack[top] : -1;

                ans = Math.max(ans, height * (i - left - 1));
            }

            stack[++top] = i;
        }

        return ans;
    }
}

func maximalRectangle(matrix []string) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }

    heights := make([]int, len(matrix[0]))
    ans := 0
    for _, row := range matrix {
        for col := 0; col < len(row); col++ {
            if row[col] == '1' {
                heights[col]++
            } else {
                heights[col] = 0
            }
        }
        area := largestRectangleArea(heights)
        if area > ans {
            ans = area
        }
    }
    return ans
}

func largestRectangleArea(heights []int) int {
    stack := make([]int, 0)
    ans := 0
    for i := 0; i <= len(heights); i++ {
        cur := 0
        if i < len(heights) {
            cur = heights[i]
        }
        for len(stack) > 0 && heights[stack[len(stack)-1]] > cur {
            // 用当前右边界和弹栈后的左边界计算本次矩形。
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            left := -1
            if len(stack) > 0 {
                left = stack[len(stack)-1]
            }
            area := height * (i - left - 1)
            if area > ans {
                ans = area
            }
        }
        stack = append(stack, i)
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(mn)$，其中 $m$、$n$ 为行列数。每行更新高度需要 $O(n)$，栈中每个下标至多入栈和出栈一次，也需要 $O(n)$。
  • 空间复杂度：$O(n)$，保存一行列高和本行下标栈，不保存历史行的高度数组。

关键点总结

[!green]

  • 列高表示以当前行为底的连续一，遇零必须断开。
  • 每个矩形都有底边，逐行计算柱状图覆盖全部候选。
  • 等高柱子可以留栈，最大宽度最终由较靠左的同高度柱子结算。

易错点总结

[!yellow]

  • LCR 040 输入是字符串数组，字符需要与 '1' 比较。
  • 遇到零只跳过而不清空列高，会把上下不连续的一连接成矩形。
  • 每行都要重新计算柱状图，最优矩形的底边不一定在最后一行。
  • 宽度使用弹栈后的左边界，公式为 i - left - 1。

相似题目

题目 难度 关联与区别
84. 柱状图中最大的矩形 困难 逐行维护连续1的高度后，每一行直接转为柱状图最大矩形。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/25732663
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！