Problem Overview
The task is to find the largest rectangle area that can be formed in a histogram. Each bar in the histogram has a width of 1, and the height of each bar is given by an array of non-negative integers.
For example, given the heights array [2, 1, 5, 6, 2, 3]
, the largest rectangle area in the histogram is 10
.
Solution Approach
The problem can be efficiently solved using a stack-based approach. This approach involves maintaining a stack to keep track of indices of the histogram bars, allowing us to calculate the maximum rectangle area in linear time. Here's a detailed breakdown of the algorithm:
1. Initialize Variables
-
len
: The length of theheights
array. -
stack
: An empty stack used to store indices of the histogram bars. -
max
: A variable to keep track of the maximum rectangle area found so far. -
h
: The height of the bar which is being popped from the stack. -
w
: The width of the rectangle formed with heighth
.
2. Iterate Through Heights Array
We iterate through the heights
array from left to right and also add a final virtual bar with height 0
at the end of the array to ensure that all bars are processed.
Steps in the iteration:
Push Current Bar's Index: For each bar, push its index onto the stack. However, before doing that, we need to ensure that the current bar is taller than the bar at the index stored at the top of the stack. If it is not, we pop bars from the stack to calculate the area of rectangles that can be formed using the bar at the popped index as the smallest bar (i.e., the height of the rectangle).
-
Pop from Stack and Calculate Area:
- Pop the top index from the stack. This index represents the height of the smallest bar in the rectangle.
- Calculate the width of the rectangle. If the stack is empty after popping, it means that the popped bar was the smallest so far, and its width extends from the beginning of the array to the current index. Otherwise, the width is determined by the distance between the current index and the index now at the top of the stack, minus one.
- Compute the area of the rectangle using the height and width and update the
max
variable if this area is larger.
3. Handle Remaining Bars in the Stack
After iterating through all bars, there might still be some bars left in the stack. These bars would have heights that were not processed because there was no shorter bar to the right. We need to process these remaining bars similarly by popping them from the stack and calculating the area.
Detailed Explanation of the Code
Here's the JavaScript code with comments explaining each part:
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
var len = heights.length;
var stack = [];
var max = 0;
var h = 0;
var w = 0;
// Iterate through the heights array
for (var i = 0; i <= len; i++) {
// Ensure the loop processes the virtual bar with height 0 at the end
while (stack.length && (i === len || heights[i] <= heights[stack[stack.length - 1]])) {
// Pop the top index from the stack
h = heights[stack.pop()];
// Calculate the width of the rectangle
w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
// Update the maximum area found so far
max = Math.max(max, h * w);
}
// Push the current index onto the stack
stack.push(i);
}
return max;
};
Complexity Analysis
- Time Complexity: O(n), where n is the number of bars in the histogram. Each bar is pushed and popped from the stack at most once.
- Space Complexity: O(n) for the stack used to keep track of indices.
Top comments (0)