84. Largest Rectangle in Histogram
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.
Example 1:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4] Output: 4
Constraints:
1 <= heights.length <= 105
0 <= heights[i] <= 104
Solutions
Solution 1: Monotonic Stack
We can enumerate the height $h$ of each bar as the height of the rectangle. Using a monotonic stack, we find the index $left_i$, $right_i$ of the first bar with a height less than $h$ to the left and right. The area of the rectangle at this time is $h \times (right_i-left_i-1)$. We can find the maximum value.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ represents the length of $heights$.
Common model of monotonic stack: Find the nearest number to the left/right of each number that is larger/smaller than it. Template:
stk = []
for i in range(n):
while stk and check(stk[-1], i):
stk.pop()
stk.append(i)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 |