Problem Description
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Key Insights
- The problem involves finding the largest rectangle that can be formed in a histogram.
- Each bar in the histogram can be treated as a potential height for rectangles.
- We can use a stack to keep track of the indices of the bars in a monotonically increasing order.
- When a bar is shorter than the bar at the top of the stack, it indicates that we can calculate the area of rectangles that can be formed with the height of the bar at the top of the stack.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
To solve this problem, we will utilize a monotonic stack to efficiently compute the maximum area of rectangles that can be formed in the histogram. The stack will help us track the indices of the bars in increasing order of their heights. When we encounter a bar that is shorter than the bar corresponding to the index at the top of the stack, we pop from the stack and calculate the area of the rectangle that can be formed with the popped height as the smallest (or limiting) height. The width of this rectangle is determined by the current index and the index of the new top of the stack after popping.