84. 柱状图中最大的矩形

🔴   🔖  栈 数组 单调栈  🔗 力扣 LeetCode

题目

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]

Output: 10

Explanation: The above is a histogram where width of each bar is 1.

The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]

Output: 4

Constraints:

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

题目大意

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入： heights = [2,1,5,6,2,3]

输出： 10

解释： 最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]

输出： 4

提示：

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4

解题思路

可以使用单调栈来维护一个递增的柱形高度序列，从而能够快速找到每根柱子左右两边的边界，计算出它能形成的最大矩形面积。

1. 遍历每个柱形

从左到右遍历柱形，如果当前柱子的高度比栈顶柱子的高度大，则继续向右扩展。否则，弹出栈顶的柱子并计算它所能形成的矩形面积。

2. 计算面积

每当遇到一个比栈顶元素高度小的柱子时，将栈顶柱子弹出，将其视为当前能够形成矩形的高度，并使用栈中的前一个柱子的索引来确定矩形的宽度范围。根据该宽度和高度来计算面积。

3. 结束时清空栈

当遍历完成后，可能栈中还有未处理的柱子。这时将栈中的柱子逐个弹出，计算面积，直到栈为空。

复杂度分析

• 时间复杂度: O(n)，其中 n 是柱子的数量。每个柱子最多会被压入和弹出栈一次，因此时间复杂度是线性的。
• 空间复杂度: O(n)，使用一个栈来存储柱子的索引，最坏情况下，栈的大小可能是 O(n)。

代码

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
	let stack = [], // 用于存储柱子的索引
		res = 0;

	// 添加一个高度为0的柱子，用来处理剩余的栈元素
	heights.push(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 === 0 ? i : i - stack[stack.length - 1] - 1;

			// 更新最大矩形面积
			res = Math.max(res, w * h);
		}

		// 将当前柱子的索引存入栈中
		stack.push(i);
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
85	最大矩形	[✓]	栈 数组 动态规划 2+
1793	好子数组的最大分数		栈 数组 双指针 2+