147. 최솟값 찾기

백준

1. 데크

from collections import deque 

#윈도우 사이즈가 l
n, l = map(int, input().split()) 
array = list(map(int, input().split()))

dq = deque() 

for i in range(n): 
  tmp = array[i] 
  #dq가 있고, dq의 마지막이 array[i]보다 클 때 꺼내기
  while dq and dq[-1] > tmp: dq.pop()
  dq.append(tmp) 
  #윈도우 크기보다 커진 단계에서 arr와 비교한 후 left pop 
  if i >= l and dq[0] == array[i - l]: dq.popleft() 
  
  print(dq[0], end=' ')

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


now 1
dq deque([])
dq deque([1])
i, array[i - l] 0 6
dq deque([1])
1 now 5
dq deque([1])
dq deque([1, 5])
i, array[i - l] 1 1
dq deque([1, 5])
1 now 2
dq deque([1, 5])
dq deque([1, 2])
i, array[i - l] 2 5
dq deque([1, 2])
1 now 3
dq deque([1, 2])
dq deque([1, 2, 3])
i, array[i - l] 3 2
dq deque([2, 3])
2 now 6
dq deque([2, 3])
dq deque([2, 3, 6])
i, array[i - l] 4 3
dq deque([2, 3, 6])
2 now 2
dq deque([2, 3, 6])
dq deque([2, 2])
i, array[i - l] 5 6
dq deque([2])
2 now 3
dq deque([2])
dq deque([2, 3])
i, array[i - l] 6 2
dq deque([2, 3])
2 now 7
dq deque([2, 3])
dq deque([2, 3, 7])
i, array[i - l] 7 3
dq deque([2, 3, 7])
2 now 3
dq deque([2, 3, 7])
dq deque([2, 3, 3])
i, array[i - l] 8 7
dq deque([3, 3])
3 now 5
dq deque([3, 3])
dq deque([3, 3, 5])
i, array[i - l] 9 3
dq deque([3, 5])
3 now 2
dq deque([3, 5])
dq deque([2])
i, array[i - l] 10 5
dq deque([2])
2 now 6
dq deque([2])
dq deque([2, 6])
i, array[i - l] 11 2
dq deque([2, 6])

2. C++

#include <cstdio>
#include <deque>
using namespace std;

int n, l, a;
deque< pair<int, int> > q;
int main() {
    scanf("%d%d", &n, &l);
    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &a);
        while (!q.empty()) {
            pair<int, int> t = q.back();
            if (t.second >= a) q.pop_back();
            else break;
        }
        q.push_back(make_pair(i, a));
        pair<int, int> t = q.front();
        if (t.first == i - l) q.pop_front(), t = q.front();
        printf("%d ", t.second);
    }
}