-
Notifications
You must be signed in to change notification settings - Fork 121
/
Largest Rectangle in histogram.py
85 lines (65 loc) · 1.84 KB
/
Largest Rectangle in 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# Python3 program to find maximum
# rectangular area in linear time
def max_area_histogram(histogram):
# This function calculates maximum
# rectangular area under given
# histogram with n bars
# Create an empty stack. The stack
# holds indexes of histogram[] list.
# The bars stored in the stack are
# always in increasing order of
# their heights.
stack = list()
max_area = 0 # Initialize max area
# Run through all bars of
# given histogram
index = 0
while index < len(histogram):
# If this bar is higher
# than the bar on top
# stack, push it to stack
if (not stack) or (histogram[stack[-1]] <= histogram[index]):
stack.append(index)
index += 1
# If this bar is lower than top of stack,
# then calculate area of rectangle with
# stack top as the smallest (or minimum
# height) bar.'i' is 'right index' for
# the top and element before top in stack
# is 'left index'
else:
# pop the top
top_of_stack = stack.pop()
# Calculate the area with
# histogram[top_of_stack] stack
# as smallest bar
area = (histogram[top_of_stack] *
((index - stack[-1] - 1)
if stack else index))
# update max area, if needed
max_area = max(max_area, area)
# Now pop the remaining bars from
# stack and calculate area with
# every popped bar as the smallest bar
while stack:
# pop the top
top_of_stack = stack.pop()
# Calculate the area with
# histogram[top_of_stack]
# stack as smallest bar
area = (histogram[top_of_stack] *
((index - stack[-1] - 1)
if stack else index))
# update max area, if needed
max_area = max(max_area, area)
# Return maximum area under
# the given histogram
return max_area
# Driver Code
if __name__ == '__main__':
hist = [6, 2, 5, 4, 5, 1, 6]
# Function call
print("Maximum area is",
max_area_histogram(hist))
# This code is contributed
# by Jinay Shah