Largest_Rectangle.py

• View this file on GitHub
• Last update: 2022-12-24 17:41:50+09:00

Code

def Largest_Rectangle(H, mode=0):
    """ ヒストグラム H における最大長方形のサイズを求める.

    H: リスト
    mode: 1 のときはその範囲も求める.
    """
    from collections import deque
    H=H+[0]
    S=deque([])
    X=H[0]
    l=r=-1
    for i in range(len(H)):
        if (not S) or H[S[-1]]<H[i]:
            S.append(i)
        else:
            while S and H[S[-1]]>=H[i]:
                j=S.pop()
                if X<H[j]*(i-j):
                    X=H[j]*(i-j)
                    l=j; r=i-1
            H[j]=H[i]
            S.append(j)

    if mode==0:
        return X
    else:
        return X,(l,r)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page