跳至主要內容

85. 最大矩形


85. 最大矩形open in new window

🔴   🔖  数组 动态规划 矩阵 单调栈  🔗 力扣open in new window LeetCodeopen in new window

题目

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'.

题目大意

给定一个由 01 组成的矩阵 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柱状图中最大的矩形open in new window[✓] 数组 单调栈
221最大正方形open in new window[✓]数组 动态规划 矩阵