[python] Stacks and Queues > Largest Rectangle

히스토그램에서 가장 큰 직사각형 크기를 찾는 문제

1. 빈 스택을 만든다.
2. 첫 번째 막대에서 시작하여 모든 막대 hist[i]에 대해 다음을 수행합니다. 여기서 ' i '는 0에서 n-1까지 존재한다.
   2-1. 스택이 비어 있거나 hist[i]가 스택 상단의 막대보다 높으면 ' i '를 밀어 스택에 넣습니다.
   2-2. 이 막대가 스택 상단보다 작으면 스택 상단이 더 큰 동안 스택 상단을 계속 제거합니다.
   2-2-1. 제거된 막대를 hist[tp]라고 합니다. hist[tp]를 가장 작은 막대로 사용하여 직사각형의 면적을 계산합니다.
   hist[tp]의 경우 '왼쪽 인덱스'는 스택의 이전(tp 이전) 항목이고 '오른쪽 인덱스'는 ' i '(현재 인덱스)입니다.
3. 스택이 비어 있지 않으면 스택에서 모든 막대를 하나씩 제거하고 제거된 모든 막대에 대해 단계(2.2 및 2.3)를 수행합니다.

def largestRectangle(histogram):
    stack = list()
  
    max_area = 0  
    index = 0
    while index < len(histogram):
        if (not stack) or (histogram[stack[-1]] <= histogram[index]):
            stack.append(index)
            index += 1
        else:
            top_of_stack = stack.pop()
            area = (histogram[top_of_stack] *
                    ((index - stack[-1] - 1)
                     if stack else index))
            max_area = max(max_area, area)
            
    while stack:
        top_of_stack = stack.pop()
        area = (histogram[top_of_stack] *
                ((index - stack[-1] - 1)
                 if stack else index))
        max_area = max(max_area, area)

    return max_area