最大矩形——单调栈+柱状图与DP两种解法对比
最大矩形——单调栈+柱状图与DP两种解法对比
适读人群：Java后端工程师、单调栈+DP综合学习者 | 阅读时长：约22分钟 | 难度：Hard
开篇故事
LeetCode 85 最大矩形，是我认为"解法最多、考点最复杂"的二维题之一。
它依托于LeetCode 84（柱状图中最大矩形），而84本身又是一道单调栈的经典题。要做85，你几乎必须先把84做好，然后一行一行地把矩阵转换成柱状图问题。
但是，85也有纯DP的解法，不需要单调栈，直接在矩阵上做DP，预处理每个格子"向左最多有多少个连续1"，然后枚举每个格子作为矩形的右边界和高度。
两种解法代表了截然不同的思路，对比着学，可以让你对"问题转化"有更深的理解。
一、题目解析
题号：LeetCode 85. Maximal Rectangle
题目描述：给定一个仅包含 0 和 1、大小为 rows × cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例：
输入：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出：6
（最大矩形是第2~3行，第2~4列，3×2=6）二、解法一：转化为84（单调栈）
2.1 核心思路
把矩阵的每一行看作"地面"，每列中从当前行向上连续的'1'的个数作为柱高，转化成"柱状图中最大矩形"（LeetCode 84）问题。
对每一行，构建一个heights数组，然后用84的单调栈解法求最大矩形。
矩阵行 i=0: heights = [1,0,1,0,0]
矩阵行 i=1: heights = [2,0,2,1,1]
矩阵行 i=2: heights = [3,1,3,2,2]
矩阵行 i=3: heights = [4,0,0,3,0]对每行的heights求最大矩形面积，所有行的最大值就是答案。
2.2 LeetCode 84（柱状图最大矩形）的单调栈解法
对每根柱子，找到它左边和右边第一个比它矮的柱子位置（left[i]，right[i]），则以第 i 根柱子为高度的最大矩形面积 = heights[i] × (right[i] - left[i] - 1)。
用单调栈（递增栈）可以在 O(n) 内同时找到所有柱子的左右边界。
public class MaximalRectangle {
/**
* 85. 最大矩形 - 转化为84（单调栈）
* 时间复杂度：O(m * n)
* 空间复杂度：O(n)
*/
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] heights = new int[n];
int maxArea = 0;
for (int i = 0; i < m; i++) {
// 更新每列的柱高（向上连续1的个数）
for (int j = 0; j < n; j++) {
heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
}
// 对当前行的heights求柱状图最大矩形
maxArea = Math.max(maxArea, largestRectangleInHistogram(heights));
}
return maxArea;
}
/**
* LeetCode 84：柱状图中最大矩形（单调栈）
*/
private int largestRectangleInHistogram(int[] heights) {
int n = heights.length;
int maxArea = 0;
Deque<Integer> stack = new ArrayDeque<>(); // 单调递增栈（存下标）
for (int i = 0; i <= n; i++) {
// 在末尾添加高度为0的哨兵，强制清空栈
int h = (i == n) ? 0 : heights[i];
while (!stack.isEmpty() && heights[stack.peek()] > h) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
}单调栈原理：
三、解法二：纯DP（左边连续1的预处理）
3.1 思路
对每个格子 (i, j)，先预处理 left[i][j] = 以 (i,j) 结尾，当前行向左连续1的个数（包括j本身）。
然后枚举每个格子作为矩形的右下角，同时枚举矩形的高度（从1行到i+1行）：
固定右下角 (i, j)，向上枚举矩形高度 h（从1到i+1）：
矩形宽度 = min(left[i][j], left[i-1][j], ..., left[i-h+1][j])（所有行中left的最小值）
面积 = h × 宽度
/**
* 85. 最大矩形 - 纯DP（左边连续1预处理）
* 时间复杂度：O(m^2 * n)
* 空间复杂度：O(m * n)
*/
public int maximalRectangleDP(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
// left[i][j] = 以(i,j)结尾向左连续1的个数
int[][] left = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
left[i][j] = (j == 0) ? 1 : left[i][j - 1] + 1;
} else {
left[i][j] = 0;
}
}
}
int maxArea = 0;
// 枚举右下角 (i, j)
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (left[i][j] == 0) continue;
int minWidth = left[i][j];
// 向上枚举高度
for (int h = 1; h <= i + 1; h++) {
minWidth = Math.min(minWidth, left[i - h + 1][j]);
maxArea = Math.max(maxArea, h * minWidth);
if (minWidth == 0) break; // 提前剪枝
}
}
}
return maxArea;
}四、两种解法对比
| 单调栈（转化为84） | 纯DP | |
|---|---|---|
| 时间复杂度 | O(m×n) | O(m²×n) |
| 空间复杂度 | O(n) | O(m×n) |
| 核心思想 | 问题转化 + 经典单调栈 | 预处理 + 枚举 |
| 代码难度 | 需要理解84 | 相对直观 |
| 推荐场景 | 面试首选（更优） | 理解DP转化过程 |
单调栈解法在时间上更优（O(mn) vs O(m²n)），而且是面试中更被推崇的解法。纯DP解法的价值在于理解"连续1的预处理"这个技巧，它在其他二维DP题里也很有用。
Mermaid：两种解法思路对比：
五、举一反三
- LeetCode 84. 柱状图中最大矩形：85的子问题，必须会
- LeetCode 221. 最大正方形：85的特殊情况（宽=高）
- LeetCode 1727. 重新排列后的最大子矩阵：矩阵变形后求最大全1矩形
六、踩坑实录
坑一：heights数组不重置
每行处理完后，heights数组是累加的（每行在上一行基础上更新）。当某列是'0'时，heights[j] 必须重置为0，不能保留上一行的值。
坑二：单调栈的哨兵
在heights末尾添加高度为0的哨兵，保证栈中剩余元素都被弹出计算。如果不加哨兵，循环结束后栈里还有元素，需要额外清空处理，容易出错。
坑三：单调栈里存下标还是高度
存下标，因为计算宽度时需要知道左边界的位置（stack.peek()），如果存高度就无法计算宽度。
七、总结
最大矩形有两种经典解法：
- 单调栈：把矩阵每行转化成柱状图，调用84的单调栈解法，时间O(mn)，是面试首选
- 纯DP：预处理连续1的宽度，枚举右下角和高度，时间O(m²n)，代码更直观
两种解法都值得掌握，前者是优化的工程实现，后者是理解原理的好工具。