[Algorithm🧬] 백준 6549 : 히스토그램에서 가장 큰 사각형

문제

일단 내가 생각한 건 옆으로 하나씩 가면서

1. 가로 1, heights[i] 짜리 사각형
2. 지금까지 가로, 온 것 중 최소 높이인 가로로 긴 사각형
3. 그리고 진짜 최대가 될 수 있는 test case 1 번의 8 같은 사각형

3개를 비교해서 최대를 구하면 되지 않을까 였는데 이걸 비교하기 위해 스택을 어떻게 이용할지..? 고민하고 있었는데 잘 안떠올라서 블로그 를 참고했다.

import sys
from collections import deque

readl = sys.stdin.readline


line = readl()
while line != '0':
    # 입력 받기
    n = 0
    heights = []
    for i, num in enumerate(map(int, line.split())):
        if i == 0:
            n = num
            continue
        heights.append(num)
    heights.append(-1) # 마지막에 스택에 남은 것 전부 프린트하기 위한 while 문 쓰는대신 -1 로 채운다.

    # 스택을 이용해서 풀기.
    stack = []
    max_area = 0

    for i in range(n + 1):
        w = i
        h = heights[i]
        # 새로 들어가는 것의 높이가 크면 해당 높이를 사용할수도 있으니 STACK 에 유지
        # 작으면, 커다란 부분에 대해서는 의미가 없으므로 pop
        while stack and heights[stack[-1]] > heights[i]:
            p = stack.pop()
            h = heights[p]
            # 지금거보다 작거나 같은게 남아있다면, 거기까지만 width 체크
            if stack:
                w = (i - 1 - stack[-1])
            # 스택이 비었다면, 현재 높이가 최소이므로 현재 높이 * i 하면 됨.
            else:
                w = i

            max_area = max(max_area, w * h)

        stack.append(i)
        # print(stack)

    print(max_area)

    line = readl().strip()