• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 with python3

17 Nov 2018

Reading time ~1 minute

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

while True:
    N, *l=list(map(int, input().split()))
    l.append(0)
    if N == 0: break
    s=[]
    a=0
    for i,h in enumerate(l):
        while s and l[s[-1]]>h:
            ih=l[s.pop()]
            # s의 높이!
            w=i-s[-1]-1 if s else i
            # i에서부터 s의 top까지의 거리를 가로길이로 한다.
            # w = i일때는 마지막일 때
            if a<w*ih: a=w*ih
        s.append(i)
    print(a)


algorithm백준python Share Tweet +1