LeetCode第85题最大矩形

85. 最大矩形

题目：

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

示例 1：

输入：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

提示：

rows == matrix.length
cols == matrix.length
0 <= row, cols <= 200
matrix[i][j] 为 ‘0’ 或 ‘1’

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

这一题最直观最暴力的解法是在矩阵中任意选两个点（x1，y1），（x2，y2）然后求这个子矩阵的面积，这样的时间复杂度大概是n的6次方，时限肯定会超。那这道题怎么解？

我们可以看一道LeetCode相似的题，也是求最大矩形的（题目：84. 柱状图中最大的矩形）这题可用用单调栈解决（题解：LeetCode第84题柱状图中最大的矩形）。知道求柱状图中最大的矩阵后我们可以用这个这道题的方法来解这道题。

class Solution {
   
    private int ans;
    private int n;
    private int m;

    public int maximalRectangle(char
1
2
3
4
5
6