자바 덱을 사용한 최소값 문제

백준문제링크

주어지는 수가 굉장히 커서 정렬을 사용할수 없다.덱을 사용하면 숫자가 정렬되는 효과를 볼수 있다.

import java.util.*;
import java.io.*;


public class Main {
// Deque에 줄 노드
  static class Node{
    public int value;
    public int index;
    Node(int value,int index){
      this.value=value;
      this.index=index;
    } 
  }
	public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine()," ");
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    st=new StringTokenizer(br.readLine()," ");
    Deque<Node> dq = new LinkedList<>();

    for(int i=0;i<N;i++){
      int now = Integer.parseInt(st.nextToken());
		// 마지막 요소가 지금 들어온거 보다 크면 최소값이 아니므로  제거한다.
      while(!dq.isEmpty()&&dq.getLast().value > now) dq.removeLast();
      // 새로운 노드를 덱에 넣어준다.
      dq.addLast(new Node(now,i));
	// 인덱스에서 M을 뺀 값이 첫째 요소의 index보다 크거나 같으면 제거해준다. 
      if(i-M>=dq.getFirst().index) dq.removeFirst();
      
      bw.write(dq.getFirst().value+" ");
    }
    bw.flush();
    bw.close();
    br.close();
  }
}