-
Notifications
You must be signed in to change notification settings - Fork 0
/
largest_rectangle_histogram.py
43 lines (34 loc) · 1.65 KB
/
largest_rectangle_histogram.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
'''
Question: https://leetcode.com/problems/largest-rectangle-in-histogram/
'''
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
'''
Maintain a stack with rules:
1. If we encounter a histogram with height > one @ top of the stack, start popping until we find a height less
than or equal to curr height.
2. How far left can curr height be extended (stored in the stack), since we need to maximize the area.
TC: O(n)
SC: O(n)
'''
# a stack to store pairs of [startIndex, height] of each histogram
stack = []
maxArea = 0
for i, ht in enumerate(heights):
# start -> index from where we can start extending the current height (how far left can we extend),
# since we have to maximize the height
start = i
# if we encounter a height > height @ top of the stack, we need to POP
while stack and stack[-1][1] > ht:
sIndex, height = stack.pop()
# height * (i - sIndex) -> area of histogram @ top of the stack
maxArea = max(maxArea, height * (i - sIndex))
# since the height @ top of stack > curr height, we can extend curr height to the left
start = sIndex
stack.append([start, ht])
# there might still be histograms in the stack which can be extended to the end of `heights` array
for i, h in stack:
# check if any of those histogram area are greater than curr maxArea
maxArea = max(maxArea, h * (len(heights) - i))
return maxArea