백준 11003번 [최솟값 찾기]

deque + 슬라이딩 윈도우

 

일정한 범위 유지 ㅡ> 슬라이딩 윈도우

범위의 앞뒤에서 사건 발생 ㅡ> deque

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

	deque<pll> mydeque;

	ll n, l;
	cin >> n >> l;
	for (ll i = 1; i <= n; i++) {
		ll x;
		cin >> x;
		ll s = mydeque.size();
		if (s == 0) {
			mydeque.push_back({ i, x });
		}
		else {
			for (ll j = s-1; j >= 0; j--) {
				if (mydeque[j].second < x) break;
				else mydeque.pop_back();
			}
			mydeque.push_back({ i, x });
		}
		while (1) {
			if (mydeque[0].first < i + 1 - l) mydeque.pop_front();
			else break;
		}
		cout << mydeque[0].second << " ";
	}

	return 0;
}