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

题目大意

解题思路

LeetCode 第 85 题 "最大矩形" 要求在一个由 1 和 0 组成的二维矩阵中找到只包含 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	最大正方形	[✓]	数组 动态规划 矩阵