from collections import *
N,L = map(int,input().split())
seq = [*map(int,input().split())]
dq = deque()
for i in range(N):
x = seq[i]
while dq:
if dq[0][1]<=i-L:
dq.popleft()
elif dq[-1][0]>=x:
dq.pop()
else:
break
dq.append((x,i))
print(dq[0][0],end=" ")
이전의 최솟값 찾기 [백준 11003번] 최솟값 찾기 (Python3) (tistory.com) 문제를 시간복잡도 O(NlogN)에 해결하였었는데, O(N)으로 개선한 코드이다.
pypy로만 제출되었던 기존의 풀이와 다르게 python으로도 제출할 수 있었고, pypy에서도 제출시간이 크게 개선되었다.
풀이를 설명하면,
1. deque를 이용한다. dq에는 항상 오름차순으로 값과 인덱스를 포함한 튜플이 배치되며, dq[0][0]가 곧 출력해야하는 값이다.
2. deque[0]의 인덱스값이 범위를 벗어나는 경우 popleft를 한다.
3. deque[-1]의 값이 현재 입력할 값보다 작은 경우 pop한다.
4. deque에 (현재 값, index)를 튜플로 삽입한다.
5. deque[0]의 값을 출력한다.
스택에 값과 인덱스를 튜플로 삽입하는 것을 통해 결과를 구한다는 점에서 [백준 6549번] 히스토그램에서 가장 큰 직사각형 (Python3) (tistory.com) 의 풀이와 유사한 부분이 있었다.
오늘의 교훈) 스택을 적절하게 활용하자.