一、题目
1、算法题目
“给定包含0和1的二维矩阵，找出只包含1的最大矩阵，返回其面积。”
题目链接：
来源：力扣（LeetCode）
链接：85. 最大矩形 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定一个仅包含 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 复制代码
二、解题
1、思路分析
这道题跟84题【柱状图中最大的矩形】很类似，不过84题是一维的，这个是二维的。
首先，说一下暴力解法：列举所有可能出现的矩形，枚举矩形所有的左上角和右下角坐标，并检查该矩形是否是面积最大的，但是这样做时间复杂度过高，会超时。我发现在学算法之前我写出来的算法都是暴利解法。。。
OK，言归正传，这道题还是可以用单调栈来解决，单调栈的特性就是如果当前元素比栈顶元素小，就加入栈，不然就将栈中的元素弹出，知道当前元素小于栈顶元素就加入。
那么就可以使用单调栈的做法，找到最高的柱子，并找到它左右的最大高度，拼接成最大的矩形，得到面积就是想要的结果。
2、代码实现
代码参考：
class Solution { public int maximalRectangle(char[][] matrix) { int m = matrix.length; if (m == 0) { return 0; } int n = matrix[0].length; 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 ? 0 : left[i][j - 1]) + 1; } } } int ret = 0; for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法 int[] up = new int[m]; int[] down = new int[m]; Deque<Integer> stack = new LinkedList<Integer>(); for (int i = 0; i < m; i++) { while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) { stack.pop(); } up[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } stack.clear(); for (int i = m - 1; i >= 0; i--) { while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) { stack.pop(); } down[i] = stack.isEmpty() ? m : stack.peek(); stack.push(i); } for (int i = 0; i < m; i++) { int height = down[i] - up[i] - 1; int area = height * left[i][j]; ret = Math.max(ret, area); } } return ret; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(mn)
其中m和n是矩阵的行数和列数。
空间复杂度： O(mn)
其中m和n是矩阵的行数和列数。
三、总结
代码与84题代码基本类似。
思路就是：
- 枚举矩形的下边界，枚举下边界的每一列的高度
- 找到最高的柱子向左右寻找最大的矩形
- 得到矩形求出面积
