[백준] 11003번 Gold 1 최솟값 찾기, C++ 코드

 

 

덱 내부를 “단조 증가 / 감소” 상태로 유지 가능하다는 특징으로 풀 수 있다.

• 최소값 문제 → 덱을 오름차순(단조 증가) 유지
• 최대값 문제 → 덱을 내림차순(단조 감소) 유지

 

#include <iostream>
#include <deque>

#define endl "\n"

using namespace std;

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

    int n, l;
    cin >> n >> l;

    deque<pair<int, int>> dq;

    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;

        while (!dq.empty() && dq.back().first >= num) {
            dq.pop_back();
        }
        
        dq.push_back({num, i});

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

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