84. Largest Rectangle in Histogram

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 <= 105
• 0 <= heights[i] <= 104

这是一道单调栈问题。实际上，暴力算法求解已经有一定难度了：

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    let max = 0
    heights.forEach((h, i) => {
        let w = 1, l=1, r=1
        while(i-l >= 0 && heights[i-l] >= h) {
            w++
            l++
        }
        while(i+r < heights.length && heights[i+r] >= h) {
            w++
            r++
        }
        max = Math.max(max, w*h)
    })
    return max
};

这个解法是优化的基础。

它的单调栈用法不太直观，在做题时很难想到。关键点仅仅在于：我们想要的是左边比自己大的数，和右边比自己大的数这一点而已。此时，问题变成了如何快速找到左右边界。

使用单调栈储存单调增序列，一旦遇到较小的数，那么比该数大的树的下标依次从栈中弹出，在弹出过程中计算面积。由于是从高到低弹出的，最低点随弹出的过程扩展，最高点则固定是遇到的较小数。

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    let max = 0, stack = []
    
    heights = [0, ...heights, 0]
    
    for (let i=0; i<heights.length; i++) {        
        if (heights[i] < heights[stack[0]]) {
            while(heights[stack[0]] > heights[i]) {
                const crt = stack.shift()
                max = Math.max((i - stack[0] - 1) * heights[crt], max)
            }
        }
        stack.unshift(i)
    }
    
    return max
};

由于解题思路难以理解，很难说自己已经掌握了单调栈，在此记录。