BOJ 11003 - 최솟값 찾기 (monotonic queue)

https://www.acmicpc.net/problem/11003

 

풀이참고

https://jason9319.tistory.com/346

 

<문제설명>

길이 n의 배열이 주어질 때, 구간 크기가 L인 모든 구간에서 순서대로 구간 최소값을 구하라

( $n<=5000000$ )

 

 

<풀이>

nlogn으로는 풀리지 않는다 (pq로는 풀리는데, ms로는 안풀림)

 

문제의도는 O(n)

 

monotonic queue에 원소의 크기순서대로 넣은 채로 슬라이딩 윈도우 하면 된다.

 

 

<코드>

typedef pair<int, int> P;
const int MAX = 5e6 + 4;

int n, l, a[MAX];
deque<P> dq;

int main() {
	FAST;
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		while (!dq.empty() && dq.front().second <= i) dq.pop_front();
		cin >> a[i];
		while (!dq.empty() && dq.back().first >= a[i]) dq.pop_back();
		dq.push_back({ a[i], i + l });
		cout << dq.front().first << " ";
	}
}

 

 

<생각>

monotonic queue는 monotonic stack의 바닥 부분의 정보가 필요할 때 사용하면 된다.

 

for문 내의 monotonic queue나 stack이 시간복잡도를 늘리지 않는 것은, 각 원소의 입장에서 생각하면 된다. 각 원소가 큐나 스택에 딱 한번 들어갔다가 최대 한 번 나오는 것을 생각해주면 쉽다.