백준 6549번. 히스토그램에서 가장 큰 직사각형 (Python)

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

풀이

스택을 이용하여 풀었다.
기본적인 원리는 idx:0부터 순회하며 stack에 집어넣는다
만약, stack의 top의 height보다 클경우 push
height보다 작거나 같을경우 아래의 과정을 거쳐 pop되고 push 진행

입력으로 "7 2 1 4 5 1 3 3"이 들어온다고 가정할 때, 들어오는대로 (idx,height)형태로 스택에 집어넣는다.

• idx :0일때, height=2는 스택이 비어있으므로 push

• idx :1일때, height=1이므로, 스택의 top의 height가 더 크므로, pop
• (2,0)을 pop할경우, 스택이 비어있게 되는데 이는 곧, idx=1번째까지 최소높이라는 뜻
• 최고높이를 갱신해준다. (heightidx = 21=2)

• idx :2, 3일때, 각각 4와 5의 높이로 이전보다 높으므로 둘다 push
  
• idx :4일때, height=1이므로, 스택의 top보다 낮다.
• (3,5)를 pop할경우, 스택이 비어있지않는데 idx:1때 설명한것처럼 pop한상태의 스택의 top
  즉, (2,4)와 idx:4 사이만큼의 직사각형의 넓이를 구해주어야 한다.
  식으로 정리하면
  - 스택에서 top을 pop했을때 스택이 비어있지 않은경우 넓이는height(idx-stk[-1][1]-1) == 5(4-2-1)=5
• (2,4)또한 idx :1의 height 4보다 크므로 pop해준다. 위의 idx :1의 경우와 같으므로 생략

• idx :5, 6 일때도 push만 작동
• 이후, 모두 스택에 push했을 경우 하나씩 차례대로 pop을 진행하며 최대값 갱신

import sys
input=sys.stdin.readline

while True:
    li=list(map(int,input().split()))
    res=0
    if li[0]==0:break
    else:li.pop(0) 
    stk=[]
    idx=0
    for i in li:
        if not stk:
            stk.append((i,idx))
            idx+=1
        else:
            if stk[-1][0]<i:
                stk.append((i,idx))
                idx+=1
            else:
                tmp_li=[]
                while stk[-1][0]>=i:
                    now_val,now_idx=stk.pop()
                    if not stk:
                        res=max(res,now_val*(idx))
                        break
                    else:
                        res=max(res,now_val*(idx-stk[-1][1]-1))
                stk.append((i,idx))
                idx+=1
    while stk:
        now_val,now_idx=stk.pop()
        if not stk:
            res=max(res,now_val*(idx))
        else:
            res=max(res,now_val*(idx-stk[-1][1]-1))
    print(res)