[BAEKJOON] 11003 최솟값 찾기 (C++)

[문제]

[조건]

[해결방법]

1. 슬라이딩윈도우

    덱을 오름차순으로 유지하며 소스코드를 진행하면된다.

    ㅡ덱의 처음이 지정된범위를 벗어난경우 제거해주는것

    ㅡ덱의 마지막을 내가 덱에 추가하고자하는 값이 최대가 되도록 유지시켜주는것

2. 세그먼트 트리

[전체소스코드]

1. 슬라이딩 윈도우

#include <iostream>
#include <algorithm>
#include <deque>
#pragma warning(disable:4996)
using namespace std;

#define fs first
#define se second

deque <pair<int, int> > q;
int ary[5000001];

int main() {
	int test, L;
	cin >> test >> L;

	for (int i = 0; i < test; i++)
		cin >> ary[i];

	for (int i = 0; i < test; i++) {
		if (!q.empty() && q.front().se < i - L + 1)
			q.pop_front();

		while (!q.empty() && q.back().fs > ary[i])
			q.pop_back();

		q.push_back(make_pair(ary[i], i));
		cout << q.front().fs << " ";
	}
}