단조 큐

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

 

단조 큐란?

큐에 들어있는 어떠한 값들의 집합이 단조성을 보이는 것

 

위의 백준 문제는 수열을 순회하면서 특정 구간에 대해 최솟값을 찾는 문제

어떤 구간에서 최솟값보다 큰 수들이 무시된다는 점에서 수열을 순회하면서 상대적으로 큰 수들을 배제하면,

구간에 알맞은 최솟값을 남길 수 있을 것이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    static class Node {
        int idx;
        int num;

        public Node() {}
        public Node(int idx, int num) {
            this.idx = idx;
            this.num = num;
        }
    }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        Node[] arr = new Node[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            arr[i] = new Node(i, Integer.parseInt(st.nextToken()));
        }

        sb.append(arr[1].num).append(" ");
        Deque<Node> deque = new ArrayDeque<>();
        int start;
        for(int i = 1; i <= N; i++) {
            start = (i - L + 1) > 0 ? (i - L + 1) : 1;

            if(deque.isEmpty()) {
                deque.addFirst(arr[i]);
                continue;
            }

            while(!deque.isEmpty() && deque.peekLast().num >= arr[i].num) {
                deque.pollLast();
            }

            deque.addLast(arr[i]);

            while(deque.peekFirst().idx < start) {
                deque.pollFirst();
            }

            sb.append(deque.peekFirst().num).append(" ");
        }

        System.out.println(sb);
    }
}