[Algorithm] 백준 BOJ 1725 히스토그램(python 파이썬)

BOJ 1725 히스토그램

문제

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

출처 - 백준 온라인 저지

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 

위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 

아래 그림의 빗금 친 부분이 그 예이다.

이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

출처 - 백준 온라인 저지

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

시간 제한 : 0.7 초
메모리 제한 : 128 MB

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. 

N은 히스토그램의 가로 칸의 수이다. 

다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 

각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

예제 입력 1

7
2
1
4
5
1
3
3

예제 출력 1

8

풀이

import sys

input=sys.stdin.readline
n = int(input())
graph = []
res = 0
cursor = 0
a = 0

for _ in range(n):
  graph.append(int(input()))

graph.append(0)
stack = [(0, graph[0])]

for i in range(1,n+1):
  cursor = i
  while stack and stack[-1][1] > graph[i]:
      cursor, temp = stack.pop()
      res = max(res, temp*(i-cursor))
  stack.append((cursor, graph[i]))
  
print(res)