85. 最大矩形

题意

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩

形，并返回其面积。

难度

困难

示例

示例 1：

085.%E6%9C%80%E5%A4%A7%E7%9F%A9%E5%BD%A2-20231001074238.png

输入：matrix = [

["1","0","1","0","0"],

["1","0","1","1","1"],

["1","1","1","1","1"],

["1","0","0","1","0"]]

输出：6

解释：最大矩形如上图所示。

示例 2：

输入：matrix = []

输出：0

示例 3：

输入：matrix = [["0"]]

输出：0

示例 4：

输入：matrix = [["1"]]

输出：1

示例 5：

输入：matrix = [["0","0"]]

输出：0

分析

本题如果直接入手会非常困难，但之前我们已经做过 084.柱状图中最大的矩形 这题，两

题之间还是有一些共性的，我们来挖掘一下。

首先，我们来看这样一个情况：

085.%E6%9C%80%E5%A4%A7%E7%9F%A9%E5%BD%A2-20231001074513.png

是不是有点眼熟，这不就是一个 heights = [3,2,2,1] 求最大矩形面积吗？

针对这种情况，我们似乎直接套用 084.柱状图中最大的矩形 的题解即可。

来看一下题目描述：

• 084 题：给定一个数组，每个值表示柱子的高度，找出能够勾勒出来的矩形的最大面

积。

• 085 题：给定一个二维矩阵，其中只包含 ‘1’ 和 ‘0’，找出只包含 ‘1’ 的矩形的最大面

积。

分析一下它们之间的关系：

• 为了解决 085 题，我们可以使用 084 题的思想。具体来说，将二维矩阵每一行视为

一个柱状图的底部，并计算从当前行开始向上的柱子高度。这样，对于每一行，我们

都可以得到一个柱状图。

• 之后，我们就可以将这个柱状图传递给解决 084 题的方法，来找到这一行为底部时

的最大矩形面积。

• 最后，遍历矩阵的每一行，找到最大的面积。

当然了，还是存在一些其他情况的，比如说 柱子 从中间层断开了怎么办？

很简单，我们按照从上到下的层次来依次统计每一行的最大矩形面积，比如说第一行，第

一行+第二行，第一行+第二行+第三行，第一行+第二行+第三行+第四行。

看下边的橙色部分。

085.%E6%9C%80%E5%A4%A7%E7%9F%A9%E5%BD%A2-20231001075623.png

• 第一次，最大矩形面积为 1；

• 第二次，最大矩形面积为 3；

• 第三次，最大矩形面积为 6；

• 第四次，最大矩形面积为 4。

第四次的最大矩形面积比第三次小，是因为第四行出现了 0，导致比最高柱子小的左右两

侧的柱子都无法计算在内。

这样子的时间复杂度为$ O(nm) $，实际上是对每行都做了一次 084.柱状图中最大的矩

形。来看题解。

class Solution {

// 主函数：寻找最大矩形

public int maximalRectangle(char[][] matrix) {

// 判断空矩阵情况

 if(matrix.length == 0) return 0;

// 创建高度数组，大小等于矩阵的列数

int[] height = new int[matrix[0].length];

int res = 0; // 最大矩形面积

// 遍历矩阵的每一行

for (char[] chars : matrix) {

// 更新当前行的高度

for (int col = 0; col < chars.length; col++) {

// 如果当前位置为'1'，则累加高度

if (chars[col] == '1')

height[col]++;

else // 否则，重置高度为 0

height[col] = 0;

}

// 对于每一行，计算最大的矩形面积，并更新 res

res = Math.max(res, largestRectangleArea(height));

}

return res; // 返回最大矩形面积

}

// 辅助函数：计算柱状图中最大的矩形面积

public int largestRectangleArea(int[] heights) {

Stack<Integer> s = new Stack<>(); // 单调递增栈

int[] lefLower = new int[heights.length]; // 存储左边第一个小于当前高度的索引

int[] rigLower = new int[heights.length]; // 存储右边第一个小于当前高度的索引

Arrays.fill(rigLower,heights.length); // 初始化为右边界

// 遍历每个柱子

for(int i = 0;i < heights.length;i++) {

// 当栈不为空且当前柱子高度小于栈顶柱子的高度

while (!s.empty() && heights[s.peek()] > heights[i]) {

// 更新右边第一个小于栈顶柱子高度的索引

rigLower[s.pop()] = i;

}

// 更新左边第一个小于当前柱子高度的索引

lefLower[i] = s.empty() ? -1 : s.peek();

// 当前柱子索引入栈

s.push(i);

}

int res = 0; // 最大矩形面积

// 计算每个柱子的最大矩形面积

for(int i = 0;i < heights.length;i++) {

res = Math.max(res, (rigLower[i] - lefLower[i] - 1) * heights[i]);

}

return res; // 返回最大矩形面积

}

}

对于给定的输入 matrix:

[

["1","0","1","0","0"],

["1","0","1","1","1"],

["1","1","1","1","1"],

["1","0","0","1","0"]

]

我们可以先计算每一行所形成的柱状图，然后使用前面描述的方法来求最大矩形面积。

具体操作如下：

1. 第一行：[1,0,1,0,0]

2. 第二行：[2,0,2,1,1]

3. 第三行：[3,1,3,2,2]

4. 第四行：[4,0,0,3,0]

接下来，对每一行都计算最大的矩形面积，然后选取这些面积中的最大值。

1. 对第一行：最大面积 = 1

2. 对第二行：最大面积 = 3 (由第二行第三列、第四列所形成的 2*1 的矩形)

3. 对第三行：最大面积 = 6 (由第三行第二列、第三列、第四列、第五列所形成的 2*3

的矩形)

4. 对第四行：最大面积 = 4 (由第四行第一列所形成的 4*1 的矩形)

因此，整个二维矩阵中的最大矩形面积是 6，所以输出为 6。

我们来看一下题解效率：

085.%E6%9C%80%E5%A4%A7%E7%9F%A9%E5%BD%A2-20231001075755.png

总结

本题其实也算是单调栈的运用，以及一个小小的思维拓展，把二维数组简化为一维数组。

这类题目还是需要多练习来强化自己的思维能力，从而快速发现破解点，将之前学过的单

调栈运用到本题中来解出答案。

力扣链接：https://leetcode.cn/problems/maximal-rectangle/