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)
'코딩테스트 준비 > [백준]' 카테고리의 다른 글
[백준] 3986번 좋은단어 - 파이썬 (0) | 2021.06.02 |
---|---|
[백준] 2841번 외계인의 기타연주 파이썬 (0) | 2021.05.30 |
[백준] 9012 파이썬 (0) | 2021.05.30 |
[백준] 1935번 - 후위표기식 2 파이썬 (0) | 2021.05.28 |
[백준] 박스채우기 1493번 c++ 풀이 (0) | 2021.05.26 |