# O(n) beautiful JS solution, please check this

• ``````/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
// 最坏情况：全部height相同，每个i进出栈各一次
// worst case: all heights are equal and each been shift and unshift once
heights.push(0) // 确保成为所有rect的右边界; now every rect must has a right border
let max = 0
const stack = [] // use shift/unshift. why? because stack[0] is better than stack[stack.length-1]
heights.forEach((height, i) => {
// 不变式：heights[0..i-1]中，所有已知边界的rect的面积都被计算并比较过了
// unchanged formula: in heights[0..i-1], every known-borders rect has been calculated its area
while (stack.length && (heights[stack[0]] > height)) {
// 注意到：当stack中存在连续相等h的i时
// notice: when there are sequencial i in stack that has the same heights[i]
// 最后出栈的i能正确计算出以该h为高的rect的左边界；
// the leftest one will lead to the correct left border of the rect that includes i
// 最先出栈的i则可能成为右边某rect的左边界
// the rightest one may become some rects left border
const h = heights[stack.shift()]
const w = stack.length ? (i - stack[0] - 1) : i
max = Math.max(max, h * w)
}
stack.unshift(i)
// 每轮过后，heights[0..i]中右边界为heights[i]的rect的面积都被计算并比较过了
// after each turn, every rect that is in heights[0..i] and use heights[i] as its right border has been calculated its are
})
return max
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.