84. Largest Rectangle in Histogram
## description
## 84. Largest Rectangle in Histogram
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:
1Input: heights = [2,1,5,6,2,3]
2Output: 10
3Explanation: The above is a histogram where width of each bar is 1.
4The largest rectangle is shown in the red area, which has an area = 10 units.Example 2:
1Input: heights = [2,4]
2Output: 4- –1 <= heights.length <= 105
- –0 <= heights[i] <= 104
Constraints:
## notes
### Intuition
A monotonic increasing stack tracks bars that could be the height of a rectangle extending to the right. When a shorter bar appears, taller bars can no longer extend further—we calculate their maximum rectangle and pop them.
### Implementation
Iterate through bars (plus a sentinel height of 0 to flush the stack). Maintain a stack of indices in increasing height order. When the current bar is shorter than the stack's top, pop and calculate the area using that bar's height. The width extends from the new stack top (or -1 if empty) to the current index. Track the maximum area.
### Edge-cases
When the stack is empty after popping, the left boundary is -1 (the bar extends to the start). The sentinel value at the end ensures all remaining bars are processed.
- –Time: O(n) — each bar pushed and popped at most once
- –Space: O(n) — stack in worst case (ascending heights)
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def largestRectangleArea(self, heights: List[int]) -> int:
5 stack = []
6 max_area = 0
7 for i in range(len(heights) + 1):
8 curr = heights[i] if i < len(heights) else 0 # sentinel height of 0 to flush the stack
9 while stack and curr < heights[stack[-1]]:
10 h_idx = stack.pop()
11 h = heights[h_idx]
12 left_idx = stack[-1] if stack else -1
13 w = i - left_idx - 1
14 max_area = max(max_area, h * w)
15 stack.append(i)
16
17 return max_area
18
19
20
21
22if __name__ == "__main__":
23 # Include one-off tests here or debugging logic that can be run by running this file
24 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
25 solution = Solution()
26