85. 最大矩形

作者：沉默王二
发布时间：2023-10-01T08:24:06.481+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

难度

困难

示例

示例 1：

输入：matrix = [

["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：6解释：最大矩形如上图所示。

示例 2：

输入：matrix = []

示例 3：

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

示例 4：

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

示例 5：

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

分析

本题如果直接入手会非常困难，但之前我们已经做过 084.柱状图中最大的矩形 这题，两题之间还是有一些共性的，我们来挖掘一下。

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

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

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

来看一下题目描述：

• 084题：给定一个数组，每个值表示柱子的高度，找出能够勾勒出来的矩形的最大面积。
• 085题：给定一个二维矩阵，其中只包含 '1' 和 '0'，找出只包含 '1' 的矩形的最大面积。

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

• 为了解决085题，我们可以使用084题的思想。具体来说，将二维矩阵每一行视为一个柱状图的底部，并计算从当前行开始向上的柱子高度。这样，对于每一行，我们都可以得到一个柱状图。
• 之后，我们就可以将这个柱状图传递给解决084题的方法，来找到这一行为底部时的最大矩形面积。
• 最后，遍历矩阵的每一行，找到最大的面积。

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

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

看下边的橙色部分。

• 第一次，最大矩形面积为 1；
• 第二次，最大矩形面积为 3；
• 第三次，最大矩形面积为 6；
• 第四次，最大矩形面积为 4。

第四次的最大矩形面积比第三次小，是因为第四行出现了 0，导致比最高柱子小的左右两侧的柱子都无法计算在内。

这样子的时间复杂度为，实际上是对每行都做了一次 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 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","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

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

具体操作如下：

• 第一行：[1,0,1,0,0]
• 第二行：[2,0,2,1,1]
• 第三行：[3,1,3,2,2]
• 第四行：[4,0,0,3,0]

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

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

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

我们来看一下题解效率：

总结

本题其实也算是单调栈的运用，以及一个小小的思维拓展，把二维数组简化为一维数组。这类题目还是需要多练习来强化自己的思维能力，从而快速发现破解点，将之前学过的单调栈运用到本题中来解出答案。

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

难度

困难

示例

示例 1：

输入：matrix = [

["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：6解释：最大矩形如上图所示。

示例 2：

输入：matrix = []

示例 3：

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

示例 4：

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

示例 5：

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

分析

本题如果直接入手会非常困难，但之前我们已经做过 084.柱状图中最大的矩形 这题，两题之间还是有一些共性的，我们来挖掘一下。

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

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

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

来看一下题目描述：

• 084题：给定一个数组，每个值表示柱子的高度，找出能够勾勒出来的矩形的最大面积。
• 085题：给定一个二维矩阵，其中只包含 '1' 和 '0'，找出只包含 '1' 的矩形的最大面积。

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

• 为了解决085题，我们可以使用084题的思想。具体来说，将二维矩阵每一行视为一个柱状图的底部，并计算从当前行开始向上的柱子高度。这样，对于每一行，我们都可以得到一个柱状图。
• 之后，我们就可以将这个柱状图传递给解决084题的方法，来找到这一行为底部时的最大矩形面积。
• 最后，遍历矩阵的每一行，找到最大的面积。

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

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

看下边的橙色部分。

• 第一次，最大矩形面积为 1；
• 第二次，最大矩形面积为 3；
• 第三次，最大矩形面积为 6；
• 第四次，最大矩形面积为 4。

第四次的最大矩形面积比第三次小，是因为第四行出现了 0，导致比最高柱子小的左右两侧的柱子都无法计算在内。

这样子的时间复杂度为，实际上是对每行都做了一次 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 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","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

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

具体操作如下：

• 第一行：[1,0,1,0,0]
• 第二行：[2,0,2,1,1]
• 第三行：[3,1,3,2,2]
• 第四行：[4,0,0,3,0]

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

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

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

我们来看一下题解效率：

总结

本题其实也算是单调栈的运用，以及一个小小的思维拓展，把二维数组简化为一维数组。这类题目还是需要多练习来强化自己的思维能力，从而快速发现破解点，将之前学过的单调栈运用到本题中来解出答案。

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

难度

困难

示例

示例 1：

输入：matrix = [

["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：6解释：最大矩形如上图所示。

示例 2：

输入：matrix = []

示例 3：

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

示例 4：

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

示例 5：

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

分析

本题如果直接入手会非常困难，但之前我们已经做过 084.柱状图中最大的矩形 这题，两题之间还是有一些共性的，我们来挖掘一下。

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

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

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

来看一下题目描述：

• 084题：给定一个数组，每个值表示柱子的高度，找出能够勾勒出来的矩形的最大面积。
• 085题：给定一个二维矩阵，其中只包含 '1' 和 '0'，找出只包含 '1' 的矩形的最大面积。

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

• 为了解决085题，我们可以使用084题的思想。具体来说，将二维矩阵每一行视为一个柱状图的底部，并计算从当前行开始向上的柱子高度。这样，对于每一行，我们都可以得到一个柱状图。
• 之后，我们就可以将这个柱状图传递给解决084题的方法，来找到这一行为底部时的最大矩形面积。
• 最后，遍历矩阵的每一行，找到最大的面积。

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

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

看下边的橙色部分。

• 第一次，最大矩形面积为 1；
• 第二次，最大矩形面积为 3；
• 第三次，最大矩形面积为 6；
• 第四次，最大矩形面积为 4。

第四次的最大矩形面积比第三次小，是因为第四行出现了 0，导致比最高柱子小的左右两侧的柱子都无法计算在内。

这样子的时间复杂度为，实际上是对每行都做了一次 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 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","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

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

具体操作如下：

• 第一行：[1,0,1,0,0]
• 第二行：[2,0,2,1,1]
• 第三行：[3,1,3,2,2]
• 第四行：[4,0,0,3,0]

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

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

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

我们来看一下题解效率：

总结

本题其实也算是单调栈的运用，以及一个小小的思维拓展，把二维数组简化为一维数组。这类题目还是需要多练习来强化自己的思维能力，从而快速发现破解点，将之前学过的单调栈运用到本题中来解出答案。

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

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412