DP/SlideMinAlgorithm.py

View this file on GitHub
Last update: 1970-01-01 00:00:00+00:00

Code

from collections import deque

def SlideMinAlgorithm(a: list, k: int) -> list:
    n = len(a)
    ans = [-1] * (n - k + 1)
    q = deque()
    q.append((a[k - 1], k - 1))
    for i in reversed(range(k - 1)):
        if q[0][0] < a[i]:
            q.appendleft((a[i], i))
    ans[0] = q[0][0]

    for i in range(1, n - k + 1):
        if q[0][1] < i:
            q.popleft()
        while q:
            if q[-1][0] <= a[i + k - 1]:
                q.pop()
            else:
                break
        q.append((a[i + k - 1], i + k - 1))
        ans[i] = q[0][0]

    return ans


def main() -> None:
    a = [3, 1, 4, 1, 5, 9, 2, 6, 5]
    print(SlideMinAlgorithm(a, 4))


if __name__ == "__main__":
    main()

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.3/x64/lib/python3.12/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.12.3/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError