LeetCode LCR 040. 最大矩形

Categories:

题目描述
思路分析
1. 解法一：逐行转化柱状图 + 单调栈（推荐）
相似题目

题目描述

✅ LCR 040. 最大矩形

思路分析

解法一：逐行转化柱状图 + 单调栈（推荐）

核心思路：

将二维矩形问题降维为一维柱状图问题，对每一行都运行 84 题的单调栈算法。

维护柱高数组 heights：从上往下逐行扫描，heights[j] 表示以第 i 行为底、向上连续 '1' 的高度。

若 matrix[i][j] == '1'，则 heights[j]++（向上累积）；若为 '0'，则 heights[j] = 0（断开重置）。

每处理完一行，以当前行为”地面”，heights 为柱高，用单调栈求该柱状图中的最大矩形面积，取全局最大值。

84 题单调栈要点：

维护严格递增栈（存下标），首尾各加一个高度为 0 的哨兵，避免边界判断。

遇到低柱时弹出栈顶，计算以弹出元素为最矮柱的矩形面积：宽 = i - stack.peek() - 1。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为矩阵的行数和列数，每行执行一次 O(n) 的单调栈。

空间复杂度：O(n)，其中 n 为矩阵列数，柱高数组与单调栈均为 O(n)。

class Solution {

    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int n = matrix[0].length;
        // 柱高数组：heights[j] 表示当前行向上连续 '1' 的高度
        int[] heights = new int[n];
        int maxArea = 0;
        for (char[] row : matrix) {
            // 逐列更新柱高
            for (int j = 0; j < n; j++) {
                heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
            }
            // 对当前行的柱高数组求最大矩形面积（84 题算法）
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

    private int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 首尾各加一个高度为 0 的哨兵，避免边界判断
        int[] h = new int[n + 2];
        System.arraycopy(heights, 0, h, 1, n);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int maxArea = 0;
        for (int i = 1; i < h.length; i++) {
            // 当前柱高小于栈顶柱高时，弹出并计算面积
            while (h[i] < h[stack.peek()]) {
                int top = stack.pop();
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h[top] * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

func maximalRectangle(matrix [][]byte) int {
	if len(matrix) == 0 {
		return 0
	}
	m, n := len(matrix), len(matrix[0])
	// 柱高数组：heights[j] 表示当前行向上连续 '1' 的高度
	heights := make([]int, n)
	maxArea := 0
	for i := 0; i < m; i++ {
		// 逐列更新柱高
		for j := 0; j < n; j++ {
			if matrix[i][j] == '1' {
				heights[j]++
			} else {
				heights[j] = 0
			}
		}
		// 对当前行的柱高数组求最大矩形面积（84 题算法）
		if area := largestRectangleInHistogram(heights); area > maxArea {
			maxArea = area
		}
	}
	return maxArea
}

func largestRectangleInHistogram(heights []int) int {
	// 首尾各加一个高度为 0 的哨兵，避免边界判断
	h := make([]int, len(heights)+2)
	copy(h[1:], heights)
	stack := []int{0}
	maxArea := 0
	for i := 1; i < len(h); i++ {
		// 当前柱高小于栈顶柱高时，弹出并计算面积
		for h[i] < h[stack[len(stack)-1]] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			width := i - stack[len(stack)-1] - 1
			if area := h[top] * width; area > maxArea {
				maxArea = area
			}
		}
		stack = append(stack, i)
	}
	return maxArea
}

相似题目

题目	难度	考察点
84. 柱状图中最大的矩形	困难	单调栈
221. 最大正方形	中等	动态规划
42. 接雨水	困难	单调栈
1504. 统计全 1 子矩形	中等	逐行拆解
363. 矩形区域不超过 K 的最大数值和	困难	前缀和
304. 二维区域和检索 - 矩阵不可变	中等	二维前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/25732663