Problem
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
Solution
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
var len = heights.length;
var stack = [];
var max = 0;
var h = 0;
var w = 0;
for (var i = 0; i <= len; i++) {
while (stack.length && (i === len || heights[i] <= heights[stack[stack.length - 1]])) {
h = heights[stack.pop()];
w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
max = Math.max(max, h * w);
}
stack.push(i);
}
return max;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).