슬라이딩 윈도우 최소값 — 단조 덱으로 O(n)

흐름

• 초기 구현: 윈도우가 찰 때마다 전체를 훑어 최소 갱신 → **O(n·L)**라서 시간 초과.
• 전환: 단조 증가 덱(monotonic queue) 유지 → 각 원소가 최대 한 번씩만 push/pop → O(n).

핵심 아이디어

1. 새 값 temp를 넣기 전, 뒤에서부터 temp 이상(>=) 은 모두 제거
   → 덱은 앞이 항상 최소값.
2. ({값, 인덱스})를 뒤에 push.
3. 윈도우 밖(인덱스 <= i - L)의 앞 원소는 pop.
4. 현재 최소값은 dq.front().first.

복잡도

• 시간: O(n) (각 원소 1회 push + 1회 pop)
• 공간: O(L)

코드 (최종)

#include <bits/stdc++.h>
using namespace std;

int n;
int l;
deque<pair<int, int>> dq;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> l;
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        
        // 이전 값이 새로 삽입되는 값보다 작다면 pop_back 을 통해 front가 항상 최소값임을 유지함
        while (!dq.empty() && dq.back().first >= temp) {
            dq.pop_back();
        }

        dq.push_back({temp, i});

        if (dq.front().second <= i - l ) {
            dq.pop_front();
        }

        cout << dq.front().first << " ";
    }

    return 0;
}

메모

• 입력이 큰 문제(예: BOJ 11003) 특성상 ios::sync_with_stdio(0); cin.tie(0);는 필수.
• 비교를 >=로 둬서 동일 값 중 더 오래된 원소를 제거하면 덱이 더 짧아져 안정적입니다.