Largest Rectangle in Histogram

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 the heights 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 height h.

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.

The above is the detailed content of Largest Rectangle in Histogram. For more information, please follow other related articles on the PHP Chinese website!