84. Largest Rectangle in Histogram（js）

佚名 6年前 (2019-04-07) 随笔 2135人围观抢沙发百度已收录

84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10
题意：求直方图围成的最大面积
代码如下：

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
   var res=0;
    var s=[];
    heights.push(0)
    for(var i=0;i<heights.length;i++){
        if(s.length===0 || heights[s[s.length-1]]<=heights[i]) s.push(i);
        else{
            var tmp=s.pop();
            res=Math.max(res,heights[tmp]*(s.length===0 ? i:(i-s[s.length-1]-1)));
            i--;
        }
    }
    return res;
};