“给定包含0和1的二维矩阵,找出只包含1的最大矩阵,返回其面积。”
题目链接:
来源:力扣(LeetCode)
链接:85. 最大矩形 - 力扣(LeetCode) (leetcode-cn.com)
给定一个仅包含 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
这道题跟84题【柱状图中最大的矩形】很类似,不过84题是一维的,这个是二维的。
首先,说一下暴力解法:列举所有可能出现的矩形,枚举矩形所有的左上角和右下角坐标,并检查该矩形是否是面积最大的,但是这样做时间复杂度过高,会超时。我发现在学算法之前我写出来的算法都是暴利解法。。。
OK,言归正传,这道题还是可以用单调栈来解决,单调栈的特性就是如果当前元素比栈顶元素小,就加入栈,不然就将栈中的元素弹出,知道当前元素小于栈顶元素就加入。
那么就可以使用单调栈的做法,找到最高的柱子,并找到它左右的最大高度,拼接成最大的矩形,得到面积就是想要的结果。
代码参考:
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;
}
}
时间复杂度 : O(mn)
其中m和n是矩阵的行数和列数。
空间复杂度: O(mn)
其中m和n是矩阵的行数和列数。
代码与84题代码基本类似。
思路就是: