-
Notifications
You must be signed in to change notification settings - Fork 1
/
LargestRectangleArea.py
38 lines (26 loc) · 1.03 KB
/
LargestRectangleArea.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
def LargestRectangleArea (heights):
stack= [-1]
maxArea= 0
for i in xrange(len(heights)):
'''keep popping from the stack while it's empty and the element in consideration is
< the last element in the stack '''
while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
lastElementIndex= stack.pop()
maxArea= max(maxArea,
heights[lastElementIndex]* (i- stack[-1]-1))
stack.append(i)
'''we went through all elements of heights array
lets check if we've something left in the stack'''
while stack[-1] != -1:
lastElementIndex= stack.pop()
maxArea= max(maxArea,
heights[lastElementIndex]* (len(heights)- stack[-1]-1))
return maxArea
if __name__ == "__main__":
t= input()
for j in range(t):
n= input()
elements= raw_input()
l= [int(i) for i in elements.split(' ')]
result= LargestRectangleArea(l)
print(result)