Solution Explanation for Largest Rectangle in Histogram

This problem asks to find the largest rectangular area in a histogram where each bar's width is 1 and the heights are given in an array. The optimal solution uses a monotonic stack.

Understanding Monotonic Stacks

A monotonic stack maintains a specific order (either strictly increasing or strictly decreasing). In this problem, we use a decreasing monotonic stack. The key idea is that when we encounter a bar shorter than the top of the stack, it means the current bar limits the maximum possible rectangle area for all bars taller than itself in the stack.

Algorithm (Monotonic Stack Approach)

1. Initialization:

   • Create an empty stack stk.
   • Initialize arrays left and right of the same size as heights. left[i] will store the index of the nearest bar to the left of i that has a height less than heights[i]. Similarly, right[i] will store the index of the nearest bar to the right of i with a height less than heights[i]. Initialize all elements in left to -1 and right to n (where n is the length of heights).

2. Iterate through heights (left to right):

   • For each bar heights[i]:
     • While the stack is not empty and the height of the top element in the stack is greater than or equal to heights[i]:
       • This means the current bar limits the rectangle for the top stack element. Update right[stack.top()] to i.
       • Pop the top element from the stack.
     • If the stack is not empty, left[i] is the index of the top element in the stack (the nearest smaller bar to the left).
     • Push i onto the stack.

3. Iterate through heights (right to left): (Alternatively, you can perform this step in a single pass as shown in some code examples)

   • Repeat a similar process as step 2, but iterate from right to left. This time, we are finding the nearest smaller bar to the right. If the stack is not empty, right[i] is the index of the top element in the stack.

4. Calculate Maximum Area:

   • Iterate through heights. For each bar i, calculate the area: heights[i] * (right[i] - left[i] - 1).
   • Keep track of the maximum area encountered so far.

5. Return the Maximum Area: Return the maximum area calculated in step 4.

Time and Space Complexity

• Time Complexity: O(n), as we iterate through the heights array twice (once left-to-right and once right-to-left) and the stack operations take amortized O(n) time.
• Space Complexity: O(n), for the stack and the left and right arrays.

Code Examples (Python):

The provided code examples effectively implement this algorithm. The one-pass solution is more concise and efficient due to the avoidance of a separate right-to-left pass. Here's a breakdown of a one-pass solution:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stack = []  # Store (index, height) pairs
        max_area = 0
        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] >= h:  #While stack is not empty and the top height is >= current height
                index, height = stack.pop()
                max_area = max(max_area, height * (i - index))
                start = index  # Update start of current bar's potential rectangle
            stack.append((start, h)) #Push current bar's info
 
        for i, h in stack:  #Handle remaining bars in the stack at the end
            max_area = max(max_area, h * (n - i))
        return max_area

This Python solution uses a single pass through the heights array. The stack stores pairs of (index, height). When a shorter bar is encountered, it processes the taller bars in the stack, calculating areas until it finds a smaller bar. This efficiently finds the largest rectangle for each bar.

The other languages (Java, C++, Go, Rust, C#) provided follow similar logic with slight syntactic differences. The core algorithm remains the same for all of them.