(파이썬) 백준 1725번 "히스토그램"

---

# 문제상황

 

 

 

 

---

# 스택을 이용한 풀이

일정 구간에서 가장 큰 직사각형의 넓이는 (해당 구간의 너비) x (해당 구간에서의 높이 최솟값) 입니다.

스택의 top이 나보다 크다면, 계속해서 pop합니다. 즉 스택의 top에는 늘 최댓값이 들어있도록 합니다.

스택을 pop 하며 뒤로 돌아가는 과정에서, 정답이 될 수 있는 모든 직사각형 넓이를 탐색할 수 있습니다.

 

현재 나의 위치에서부터 뒤로 탐색하는 것이기 때문에, 뒤로 가면 갈수록 높이(= 스택에서 pop한 값)는 낮아집니다.

즉, (뒤로 탐색한 거리) x (pop한 값)이 직사각형 넓이가 됩니다.

import sys
input = sys.stdin.readline

n = int(input())
stk = []
l = 0
ans = 0

for r in range(n):
    l = r
    x = int(input())

    while stk and stk[-1][1] > x:
        l, y = stk.pop()
        ans = max(ans, y * (r - l))
    stk.append((l, x))

while stk:
    l, y = stk.pop()
    ans = max(ans, y * (n - l))

print(ans)