84. Largest Rectangle in Histogram(js)

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.

 

84. Largest Rectangle in Histogram(js)
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

 

84. Largest Rectangle in Histogram(js)
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;
};

 

上一篇:hdu 4568 Hunter


下一篇:vue项目中的防抖、节流