본문 바로가기

코딩테스트 준비/[백준]

[백준] 1725 파이썬 - 히스토그램

https://www.acmicpc.net/problem/1725

 

1725번: 히스토그램

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은

www.acmicpc.net

 

[코드]

import sys
N = int(sys.stdin.readline())
histogram = []
[histogram.append([i + 1, int(sys.stdin.readline())]) for i in range(N)]
histogram.append([N+1,0])

stack = [[0, 0]]
answer = 0
for i in range(1, N+2):
    while stack and stack[-1][1] > histogram[i-1][1]:
        _, h = stack.pop()
        w = i - (stack[-1][0] + 1)
        answer = max(answer, w * h)        
    stack.append(histogram[i-1])

print(answer)