"""
main idea: 1. keep a mono increasing stack,
2. until current height is shorter than ones on top of stack, keep setting top stack's height as max height, difference between current idx and next stack top as width, caculate current area.
3.keep popping off lower height as target height and get corresponding width to update max area.
4. Note preprocessing st = [-1] and add one more 0 height to H so we can reach all the way to end height.
"""
class Solution:
# time O(N) space O(N)
def largestRectangleArea(self, H: List[int]) -> int:
st = [-1]
res = 0
H.append(0)
n = len(H)
for i in range(n):
while H[i] < H[st[-1]]:
print(st)
h = H[st.pop()]
w = i -st[-1] - 1
#print(h,w,st)
res = max(h*w,res)
st.append(i)
H.pop()
return res