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.
Example
Given bar heights of histogram [2,1,5,6,2,3]
Largest area of rectangle - 10
JavaScript Code
function largestRectangleArea(height) { if (height == null || height.length == 0) { return 0; } var stack = []; var max = 0; var i = 0; while (i < height.length) { //push index to stack when the current height is larger than the previous one if (stack.length == 0 || height[i] >= height[stack[stack.length - 1]]) { stack.push(i); i++; } else { //calculate max value when the current height is less than the previous one var p = stack.pop(); var h = height[p]; var w = stack.length == 0 ? i : i - stack[stack.length - 1] - 1; max = Math.max(h * w, max); } } while (stack.length!=0) { var p = stack.pop(); var h = height[p]; var w = stack.length == 0 ? i : i - stack[stack.length - 1] - 1; max = Math.max(h * w, max); } return max; } console.log(largestRectangleArea([2,1,5,6,2,3]));
this is very unclear
ReplyDelete