최솟값 찾기

구간의 최솟값을 N번 찾는데 구간이 한칸씩 오른쪽으로 이동하는 형태이다.

그냥 세그트리를 쓰면 NlogN이 걸려서 될지 안될지 확실하지 않다.

deque라는 자료구조를 써서 풀 수 있다.

deque는 앞에도 뒤에도 push와 pop을 할 수 있는 자료구조이다.

deque의 front를 구간의 최솟값으로 놓을 것이다.

새로운 수가 들어오면 우선 현재 최솟값인 deque의 front의 인덱스가 i-L+1보다 큰지 판단하고 아니면 pop_front를 해준다.

그리고 새로 들어온 수를 deque의 back에서부터 비교하면서 새로 들어온 수보다 큰 값들을 전부 pop_back으로 없애준다.

이렇게 해도 되는 이유는 새로 들어온 수가 구간의 가장 오른쪽에 있는 수이기 때문에 구간이 한칸씩 오른쪽으로 이동할 때 계속 쓰일텐데 이전에 이미 deque에 있는 값들이 이 값보다 작으면 어차피 최소가 될 수 없기 때문에 pop을 해버려도 된다.

이런 식으로 새로운 수가 들어오면 deque의 앞과 뒤에서 pop을 시키고 새로운 수를 push_back으로 넣어주면 된다.

#include<stdio.h>
#include<queue>
using namespace std;
int N,L;
long long arr[5000004];
deque<pair<long long,int>> dq;
int main()
{
    scanf("%d %d",&N,&L);
    for(int i=1;i<=N;i++)
    {
        scanf("%lld",&arr[i]);
    }
    for(int i=1;i<=N;i++)
    {
        if(!dq.empty())
        {
            if(i-L+1>dq.front().second) dq.pop_front();
        }
        while(!dq.empty() && dq.back().first>arr[i]) dq.pop_back();
        dq.push_back(make_pair(arr[i],i));
        printf("%lld ",dq.front().first);
    }
}

해결 코드이다.