84. 柱状图中最大的矩形 🟥
题目
leetcode 困难
题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
题解
解题思路
我们需要维护一个高度单调递增的栈（栈里存的是柱子的索引）：
- 走上坡路（入栈）：如果当前柱子比栈顶的柱子高，说明栈顶的柱子还能继续向右延伸，咱们先别急着算它的面积，把它（的索引）乖乖压入栈中。
- 走下坡路（出栈并计算）：如果遇到一个柱子比栈顶的矮，好戏上演了！
- 这说明栈顶柱子的“右边界”找到了！（就是当前这个矮柱子）。
- 那它的“左边界”是谁呢？因为栈是单调递增的，所以栈顶下面压着的那个元素，就是它左边第一个比它矮的柱子！
- 左右边界都有了，立刻把栈顶弹出，计算它的面积。
- 一直弹出，直到当前柱子不再比栈顶矮，再把它入栈。
复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(N)
js
function largestRectangleArea(heights) {
let maxArea = 0
// 技巧：在数组首尾各加一个 0 作为“哨兵”
// 首部 0：防止栈空，提供绝对的左边界
// 尾部 0：强行让所有仍在栈里的元素出栈并结算
const newHeights = [0, ...heights, 0]
// 栈里存放的是索引
const stack = []
for (let i = 0; i < newHeights.length; i++) {
console.log('♻️ i', i, '【', newHeights[i], '】')
console.log(
'stack',
stack.map(idx => `${idx}【${newHeights[idx]}】`).toString(),
)
// 如果遇到了“矮子”（当前高度 < 栈顶高度），说明栈顶柱子的右边界确定了
while (
stack.length > 0 &&
newHeights[i] < newHeights[stack[stack.length - 1]]
) {
// 1. 被结算的柱子出栈，它是我们要计算的高
const hIdx = stack.pop()
const h = newHeights[hIdx]
console.log('出栈柱子', hIdx, '【', h, '】')
// 2. 此时的新栈顶，就是被弹出柱子的“左边界”
const leftIdx = stack[stack.length - 1]
// 3. 当前柱子 i，就是被弹出柱子的“右边界”
// 宽度 = 右边界 - 左边界 - 1
const w = i - leftIdx - 1
console.log('左边界', leftIdx, '【', newHeights[leftIdx], '】')
// 4. 计算面积并挑战最大值
maxArea = Math.max(maxArea, h * w)
}
console.log('maxArea', maxArea)
// 走上坡路或平路，直接入栈等待未来的右边界
stack.push(i)
console.log(
'stack',
stack.map(idx => `${idx}【${newHeights[idx]}】`).toString(),
)
}
return maxArea
}
console.log('🌰', largestRectangleArea([2, 1, 5, 6, 2, 3]))
console.log('----------------')
console.log('🌰', largestRectangleArea([2, 4]))执行结果
♻️ i 0 【 0 】
stack
maxArea 0
stack 0【0】
♻️ i 1 【 2 】
stack 0【0】
maxArea 0
stack 0【0】,1【2】
♻️ i 2 【 1 】
stack 0【0】,1【2】
出栈柱子 1 【 2 】
左边界 0 【 0 】
maxArea 2
stack 0【0】,2【1】
♻️ i 3 【 5 】
stack 0【0】,2【1】
maxArea 2
stack 0【0】,2【1】,3【5】
♻️ i 4 【 6 】
stack 0【0】,2【1】,3【5】
maxArea 2
stack 0【0】,2【1】,3【5】,4【6】
♻️ i 5 【 2 】
stack 0【0】,2【1】,3【5】,4【6】
出栈柱子 4 【 6 】
左边界 3 【 5 】
出栈柱子 3 【 5 】
左边界 2 【 1 】
maxArea 10
stack 0【0】,2【1】,5【2】
♻️ i 6 【 3 】
stack 0【0】,2【1】,5【2】
maxArea 10
stack 0【0】,2【1】,5【2】,6【3】
♻️ i 7 【 0 】
stack 0【0】,2【1】,5【2】,6【3】
出栈柱子 6 【 3 】
左边界 5 【 2 】
出栈柱子 5 【 2 】
左边界 2 【 1 】
出栈柱子 2 【 1 】
左边界 0 【 0 】
maxArea 10
stack 0【0】,7【0】
🌰 10
----------------
♻️ i 0 【 0 】
stack
maxArea 0
stack 0【0】
♻️ i 1 【 2 】
stack 0【0】
maxArea 0
stack 0【0】,1【2】
♻️ i 2 【 4 】
stack 0【0】,1【2】
maxArea 0
stack 0【0】,1【2】,2【4】
♻️ i 3 【 0 】
stack 0【0】,1【2】,2【4】
出栈柱子 2 【 4 】
左边界 1 【 2 】
出栈柱子 1 【 2 】
左边界 0 【 0 】
maxArea 4
stack 0【0】,3【0】
🌰 4