[백준] 6549 히스토그램에서 가장 큰 직사각형 - python

문제 링크
https://www.acmicpc.net/problem/6549

시도 1. 메모리 초과

import sys
sys.setrecursionlimit(10000)

def findArea(heights):
  if len(heights) == 0:
    return 0
  width = len(heights)
  minHeight = min(heights)
  minIndex = heights.index(minHeight)
  return max(findArea(heights[:minIndex]), findArea(heights[minIndex+1:]), minHeight * width)

while True:
  hist = list(map(int, input().split()))
  n = hist[0]
  heights = hist[1:]
  if n == 0 :
    break
  print(findArea(heights))

• 재귀 스택 제한 초과로 실패

시도2. 성공

import sys
input = sys.stdin.readline

def maxSize():
    max_size = 0
    stack = []

    for i in range(n):
        left = i
        while stack and stack[-1][0] >= heights[i]:
            h, left = stack.pop()
            tmp_size = h * (i - left)
            max_size = max(max_size, tmp_size)
        stack.append([heights[i],left])
        
    for h, point in stack:
        max_size = max(max_size, (n-point)*h)

    return max_size

while True:
    n, *heights = map(int, input().split())
    if n == 0: 
        break
    print(maxSize())

• 접근방법 : 스택
• 시간복잡도 : O(n)