Skip to main content

84. Largest Rectangle in Histogram

分析

以某一height作为最高hight的最大值
获得所有height的可能 -> 取最大

从暴力解理解, 利用单调栈进行优化

单调栈解决的需求
获得第一个小于当前height 的 index

题解

暴力

function largestRectangleArea(heights: number[]): number {
let ans = 0
for (let i = 0; i < heights.length; i++) {
let l = i
while (l >= 0 && heights[l] >= heights[i]) {
l--
}
let r = i
while (r < heights.length && heights[r] >= heights[i]) {
r++
}
ans = Math.max(ans, (r - l - 1) * heights[i])
// console.log(l, r)
/*
-1 1
-1 6
1 4
2 4
1 6
4 6
*/
}
return ans
};

单调栈优化

function largestRectangleArea(heights: number[]): number {
let ans = 0
const leftFirstSmallerIndex = [],
rightFirstSmallerIndex = []
const monoStack = []
for (let i = 0; i < heights.length; i++) {
const currentHeight = heights[i]
while (monoStack.length && heights[monoStack[monoStack.length - 1]] >= currentHeight) {
monoStack.pop()
}
leftFirstSmallerIndex[i] = monoStack.length ? monoStack[monoStack.length - 1] : -1
monoStack.push(i)
}
monoStack.length = 0
for (let i = heights.length - 1; i >= 0; i--) {
const currentHeight = heights[i]
while (monoStack.length && heights[monoStack[monoStack.length - 1]] >= currentHeight) {
monoStack.pop()
}
rightFirstSmallerIndex[i] = monoStack.length ? monoStack[monoStack.length - 1] : heights.length
monoStack.push(i)
}
// console.log(leftFirstSmallerIndex, rightFirstSmallerIndex)
/**
[ -1, -1, 1, 2, 1, 4 ]
[ 1, 6, 4, 4, 6, 6 ]
*/
for (let i = 0; i < heights.length; i++) {
ans = Math.max(ans, (rightFirstSmallerIndex[i] - leftFirstSmallerIndex[i] - 1) * heights[i])
}
return ans
}