[백준 6549] 히스토그램에서 가장 큰 직사각형 - Python(파이썬)

스택을 활용함

import sys


def solution(data):
    arr = data[1:]
    stack = []
    my_max = 0

    for idx, value in enumerate(arr):
        my_idx = idx
        while stack and stack[-1][0] >= value:
            h, my_idx = stack.pop()
            my_max = max(my_max, (idx - my_idx) * h)

        stack.append((value, my_idx))

    for h, idx in stack:
        my_max = max(my_max, (n - idx) * h)

    print(my_max)


while True:
    data = list(map(int, sys.stdin.readline().split()))
    n = data[0]

    if n == 0:
        break

    solution(data)