柱状图中最大的矩形

[Cosen95]

leetcode: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

[Cosen95]

暴力求解

遍历heights数组，每次更新高度的最小值minHeight，然后面积=长（j-i+1） * 宽（minHeight）

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    let maxArea = 0;
    const len =  heights.length;
    for(let i = 0; i < len; i++) {
        let minHeight = Number.MAX_SAFE_INTEGER;
        for(let j = i; j < len; j++) {
            minHeight = Math.min(minHeight, heights[j])
            maxArea = Math.max(maxArea, minHeight*(j-i+1))
        }
    }
    return maxArea
};

栈顶法

维护一个栈，遍历数组，遇到比当前栈顶大的元素就压入栈(压入的是索引)，否则就取出栈顶元素进行计算(以当前栈顶元素为高度的最大矩形面积)。

此时的高是：栈顶元素的值（heights[stack.pop()]），宽是：当前索引 - 栈顶元素的索引 - 1(i - stack[stack.length - 1] -1)。

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    let maxArea = 0;
    let stack = [-1]
    const len =  heights.length;
    for(let i = 0; i < len; i++) {
        while(stack.length > 1 && heights[stack[stack.length - 1]] >= heights[i]) {
            maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack[stack.length - 1] -1))
        }
        stack.push(i)
    }
    while(stack.length > 1) {
         maxArea = Math.max(maxArea, heights[stack.pop()] * (heights.length - stack[stack.length - 1] -1))
    }
    return maxArea
};