85. 最大矩形
85. 最大矩形
🔴 🔖 栈
数组
动态规划
矩阵
单调栈
🔗 力扣
LeetCode
题目
Given a rows x cols
binary matrix
filled with 0
's and 1
's, find the largest rectangle containing only 1
's and return its area.
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = [["0"]]
Output: 0
Example 3:
Input: matrix = [["1"]]
Output: 1
Constraints:
rows == matrix.length
cols == matrix[i].length
1 <= row, cols <= 200
matrix[i][j]
is'0'
or'1'
.
题目大意
给定一个由 0
和 1
组成的矩阵 matrix
,找出只包含 1
的最大矩形,并返回其面积。
解题思路
检查矩阵是否为空。
初始化一个数组
heights
,用于存储当前行的高度。将每一行视为基于上方连续
1
的高度。如果当前元素是1
,则其高度等于当前行的1
的数量;如果是0
,则高度为0
。- 例如,给定矩阵:对应的高度矩阵为:
[ ["1", "0", "1", "0", "0"], ["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] ]
- 例如,给定矩阵:
遍历每一行,更新
heights
数组。对每一行调用
largestRectangleArea
函数计算最大矩形面积。- 对于每一行的高度数组,可以使用单调栈来计算最大矩形面积。
- 使用栈来维护高度的索引,确保栈中的高度是单调递增的。遍历高度数组,如果当前高度小于栈顶元素,计算以栈顶高度为最小高度的矩形面积,并更新最大面积。
- 通过遍历高度数组,计算以每个高度为最小高度的矩形面积。
复杂度分析
- 时间复杂度:
O(m * n)
,其中m
是矩阵的行数,n
是列数。每行的最大矩形计算是O(n)
。 - 空间复杂度:
O(n)
,用于存储高度数组和栈。
代码
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function (matrix) {
if (!matrix.length || !matrix[0].length) return 0;
const heights = new Array(matrix[0].length).fill(0);
let maxArea = 0;
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
// 更新当前行的高度
heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
}
maxArea = Math.max(maxArea, largestRectangleArea(heights));
}
return maxArea;
};
var largestRectangleArea = function (heights) {
const stack = [];
let maxArea = 0;
heights.push(0); // 在数组末尾添加0以清空栈
for (let i = 0; i < heights.length; i++) {
while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
const h = heights[stack.pop()];
const w = stack.length ? i - stack[stack.length - 1] - 1 : i;
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
return maxArea;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
84 | 柱状图中最大的矩形 | [✓] | 栈 数组 单调栈 | |
221 | 最大正方形 | [✓] | 数组 动态规划 矩阵 |