from sys import stdin
input = stdin.readline
n = int(input())
rod = [0]*n
for i in range(n):
rod[i] = int(input())
result = 0
stack = []
for i in range(n):
while stack and rod[stack[-1]] > rod[i]:
h = rod[stack.pop()]
w = i if not stack else i-stack[-1]-1
result = max(result, h*w)
stack.append(i)
while stack:
h = rod[stack.pop()]
w = n if not stack else n -stack[-1] -1
result = max(result, h*w)
print(result)스택에 인덱스 값을 저장하면서 나간다. 만약 스택에 저장된 인덱스의 막대 크기보다 작은 크기의 인덱스 값이 들어온다면 뒤에서 부터 pop 하면서 넓이를 구하게 된다.
이때 작은 값이 들어와야 pop()을 진행하는 것이므로 현재 막대의 높이는 pop() 진행하면서 작아지게 된다. 즉 pop() 진행 할때 마다 최대 높이인 것이다. 따라서 높이는 pop()해서 나온 인덱스 값에 해당하는 막대의 크기이다.
너비의 경우 우선 현재 pop()이 한 번도 진행되지 않았다고 생각해보면 Stack에는 값이 순서대로 나열되어 있을것이다. pop()을 처음 진행하는 경우를 보면 당연히 for 문을 통해 진행하고 있는 i값보다 1 작은 값이다.
따라서 i - stack[-1]을 하면 w 값은 1이다. 즉 너비가 1이다. 다만 위 코드에서는 h를 구하기 위해 pop()을 했으므로 -1을 해야한다.
그 다음 연속으로 pop()을 해야한다고 생각해보자 그러면 i - stack[-1]-1 을 하면 w는 2이다.
숫자로 예를 들어보면 현재 스택에는 (1, 2, 3, 4) 이렇게 저장되어있고 i 가 5라고 가정한다. 5 인덱스의 막대가 3,4 인덱스의 막대보다 작다면 pop()을 두번 진행하게 된다.
pop()을 진행하면 인덱스 4의 막대의 높이가 h이고 w = 1이다.
pop()을 다시 진행하면 인덱스 3의 막대의 높이가 h이고 w = 2이다.
이런식으로 스택에는 막대의 높이가 커지거나 같은 순으로 저장되어 있으므로 뒤에서 부터 pop() 하면서 넓이를 계산하는 방식이다.
이렇게 계산을 진행하면서 히스토그램의 최대 넓이를 구할 수 있다.
마지막에 stack이 계속해서 증가하다 끝나는 경우나 stack에 저장되어 있는 막대의 높이보다 작은 값이 들어오지 않은 경우는 stack을 비워줌으로서 나머지 막대에 대한 히스토그램 넓이를 구해준다.
참고한 사이트 (https://c4u-rdav.tistory.com/70)
백준 오큰수와 같은 스택 응용 문제. 오큰수와 비슷하지만 반대의 개념이다.
둘다 Stack에 값을 저장하는 방식이 아닌 index를 stack에 저장하지만
오큰수는 작을 때는 스택에 저장했다가 큰 수가 오면 pop 하면서 진행했다면
이 문제는 커질 때는 스택에 저장했다가 작은 수가 오면 pop 하면서 진행한다.
