최솟값 찾기

만약 2 3 6 이 있는데 2를 푸시하려면 2보다 큰 수를 다 pop()한다.

i - L + 1 -> 윈도우 크기가 넘치면 popleft()한다.

12 3
1 5 2 3 6 2 3 7 3 5 2 6

1. [1] -> 1
2. [1, 5] -> 1
3. [1, 2] -> 1
4. [2, 3] -> 2
5. [2, 3, 6] -> 2
6. [2, 2] -> 2
7. [2, 3] -> 2
8. [2, 3, 7] -> 2
9. [3, 3] -> 3
10. [3, 5] -> 3
11. [2] -> 2
12. [2, 6] -> 2

deque모듈을 활용하여 쉽게 풀 수 있다.

import sys
from collections import deque
input = sys.stdin.readline

N, L = map(int, input().split())
arr = list(map(int, input().split()))

q = deque()
for i in range(N):
    while q and q[-1][0] > arr[i]:
        q.pop()
    while q and q[0][1] < i - L + 1:
        q.popleft()
    q.append((arr[i], i))
    print(q[0][0], end=" ")