303. 히스토그램

백준

1. 스택

import sys
input=sys.stdin.readline
n = int(input())
height = [int(input()) for _ in range(n)]

result=0
cursor=0
a=0
height.append(0)
stack=[(0, height[0])]
for i in range(1, n + 1):
  cursor=i
  while stack and stack[-1][1] > height[i]: #작아지면 거기서 계산
      cursor,temp = stack.pop()
      result = max(result, temp * (i - cursor))
  stack.append((cursor, height[i]))
  
print(result)