최소값 찾기 - 11003번

해결방법

세그먼트 트리로 안 풀렸다.세그먼트 트리로는 정말 힘들다그래서 우선순위큐로 풀었다. 근데 이것도 겨우겨우 시간 통과했다.
우선순위큐는 최대값을 반환하므로 최소값을 찾기 위해 {-값, index}를 input으로 받는다.

priority_queue<pair<int,int>> pq; // { -값, index }

그리고 최솟값의 인덱스가 i - L + 1라면, pq.top().first를 출력하고 아니라면 해당 인덱스가 나올때까지 반복한다.

전체코드

#include<iostream>
#include<queue>
using namespace std;
priority_queue<pair<int, int>> pq;
int N, L, A;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N >> L;
    for (int i = 1; i <= N; ++i) {
        cin >> A;
        pq.push({ -A, i });
        while (pq.top().second < i - L + 1) pq.pop();
        cout << -pq.top().first << ' ';
    }
    return 0;
}