(11003) 최솟값 찾기

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

단계별로 풀어보기

38단계(스택, 큐, 덱 2) 6번째

 

 

 

구간 내 최소, 최대 등을 찾는 쿼리는 추후 나올 새그먼트 트리 자료구조를 이용하면 효율적으로 구할 수 있지만 상황에 따라 덱 최댓값 트릭을 쓸 수 있다. 기본적인 아이디어는 모노톤 스택처럼 덱 내부를 정렬하여 그 과정의 정보를 사용하는 것이다.

스택 말고 덱이여야 하는 이유는 탐색 범위가 정해져 있기 때문이다. 이 문제 기준으로 i번째 원소라면 i-l+1번 원소까지만 의미가 있기 때문에, 덱의 앞에서부터 쌓이는 오래된 원소를 제거할 필요가 있다. 만약 유효한 원소 범위가 수열의 끝까지(무한대)라면 덱의 앞에서 pop할 필요 없이 스택을 이용한 트릭과 같아질 것이다.

 

 

 

#include <iostream>
#include <deque>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, l;
  
  cin >> n >> l;
  
  deque<pair<int,int>> dq;
  
  for(int i=1;i<=n;i++){
    int a;
    
    cin >> a;
    
    while(!dq.empty() && dq.back().first>a)  dq.pop_back();
    
    dq.push_back({a,i});
    
    while(dq.front().second<i-l+1)  dq.pop_front();
    
    cout << dq.front().first << " ";
  }
  
  return 0;
}