슬라이딩 윈도우 + 덱

최솟값 찾기

슬라이딩 윈도우 방식으로 풀면 되는 문제입니다.

import sys
from collections import deque
input = sys.stdin.readline
n, l = map(int, input().split())
lst = list(map(int, input().split()))
q = deque()
# 맨 처음 값 Di = Ai-L+1 ~ Ai 은 i <= 0은 무시되기 때문에 현재 리스트에 담긴 값의 맨 처음값임
q.append([lst[0], 0])
print(q[0][0], end = ' ')
# 1. 큐의 맨 뒷값이 현재 값보다 크다면 pop()
2. l의 범위를 넘는다면 pop()
3.리스트의 맨 앞값이 가장 작은 값임 
for i in range(1, len(lst)):
	while q and q[-1][0] > lst[i]:
		q.pop()
	while q and q[0][1] < i - l + 1:
		q.popleft()
	q.append([lst[i], i])
	print(q[0][0], end = ' ')