1.题目基本信息

1.1.题目描述

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

1.2.题目地址

https://leetcode.cn/problems/maximal-rectangle/description

2.解题方法

2.1.解题思路

动态规划+单调栈，可以参考Leetcode 84. 柱状图中最大的矩形

2.2.解题步骤

第一步，边界值判断

第二步，构建left矩阵，left[i][j]为matrix[i][j]处向左连续为1的个数（包括本身）

第三步，遍历每一列，使用最大矩阵的方法求每一列的各个元素能组成的最大矩阵的面积。对于每一列的遍历，目标是构建up和down两个数组，up[i]为j列的i处上面的第一个小于left[i][j]的行索引，down指i处下面的第一个小于left[i][j]的行索引，其中-1和rows相当于链表中的哑结点。中间使用单调栈工具，将与i处相邻且大于left[i][j]的元素pop掉，最后栈顶元素即为目标值。对于down，pop的元素对应的索引处的值一定是i，可以用反证法进行证明。构建每列的up和down后，遍历计算面积最大值即可

第四步，返回结果

3.解题代码

Python代码

C++代码

4.执行结果