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.
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; };