[WEEK02] 16일차. 히스토그램에서 가장 큰 직사각형

6549 히스토그램에서 가장 큰 직사각형

hin1209 님의 풀이를 참고하였다.

히스토그램에서 만들 수 있는 최대 너비를 구하는 문제인데,
히스토그램의 인덱스와 높이를 스택에 저장(append)하다가,

스택에 있는 높이보다 낮은 히스토그램을 만나면
while문을 돌려가며 pop을 하고,
pop한 값의 높이값(popped[1])과
(현재 인덱스 - 스택에 꼭대기에 있는 값의 인덱스 - 1)을 너비로 해서 곱해준다.

이렇게 하면 pop을 하면서 스택에 쌓여있는 값의 인덱스가 1씩 줄어들면서 너비가 1씩 증가하고, 높이값은 pop한 값의 높이(현재 만난 히스토그램보다 높은)를 사용하기 때문에 이것을 반복하며 최댓값을 계속 갱신하면 된다.
스택이 비어있게 되면 마지막으로 (현재 인덱스 - 1)을 밑변으로 해서 넓이를 구하면 된다.

이 과정을 마치고 마지막에 스택에 값이 남아있다면 같은 방법으로 나머지 블록에 대한 넓이 계산을 진행한다.

import sys

input = sys.stdin.readline

while True:
    h_height = list(map(int, input().split()))
    if h_height[0] == 0:
        break
    stack = []
    n = h_height[0]
    max_area = 0
    for i in range(1, n+1):
        # 스택에 들어간 게 마주친 것보다 크다면,
        # 높이 하나씩 빼가면서 인덱스를 사용해 너비와 곱해서 맥스값 갱신 
        while stack and stack[-1][1] > h_height[i]:
            popped = stack.pop()
            if stack:
                width = i - stack[-1][0] - 1
            else:
                width = i - 1
            max_area = max(max_area, popped[1] * width)
        stack.append((i, h_height[i]))
    # 검사 후 스택에 뭔가 남아있다면, 나머지 블록에 대해 넓이 계산 진행
    while stack:
        popped = stack.pop()
        if stack:
            width = n - stack[-1][0]
        else:
            width = n
        max_area = max(max_area, popped[1] * width)
    print(max_area)