[Platinum / 11003] 최솟값 찾기

문제 링크

---

🔷 분류

자료 구조, 우선순위 큐, 덱, 덱을 이용한 구간 최댓값 트릭

✒️ 문제 설명

N개의 수 A₁, A₂, …, A_N과 L이 주어진다.

D_i = A_i-L+1 ~ A_i 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 A_i는 무시하고 D를 구해야 한다.

⬅️ 입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 A_i가 주어진다. (-10⁹ ≤ A_i ≤ 10⁹)

➡️ 출력

첫째 줄에 D_i를 공백으로 구분하여 순서대로 출력한다.

💻 코드 (C++)

#include <iostream>
#include <utility>
#include <deque>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N, L;
	cin >> N >> L;
	deque<pair<int, int>> D;
	
	for(int i = 0; i < N; i++) {
		int now; 
		cin >> now;
		while(!D.empty() && D.back().first > now) { 
			D.pop_back();
		}
		D.push_back({now, i});
		if(D.front().second <= i-L) { // 범위 벗어나면
			D.pop_front();
		}
		cout << D.front().first << " ";
	}
	return 0;
}