[Algorithm] sliding window

sliding window
O(N+K)

(N: 배열의 크기, K: 고정된 크기)

큐에 하나씩 집어넣으며 사용한다.

별도로 정렬을 사용하지 않는 덱을 사용할 수 있다.

사진 출처 : https://learning-e.tistory.com/36

 

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

11003번: 최솟값 찾기

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

public class Main {
    public static void main(String[] args) {
        try {
            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()), L=Integer.parseInt(st.nextToken());
			// N: 배열의 크기, L: 고정된 크기
            
            Deque<Node> q = new LinkedList<>();
            st = new StringTokenizer(br.readLine());

            for(int i=0; i<N; i++){
                long now = longData(st);

                // 비어있지않은 상태에서, 덱에 들어있는 값이 현재 가지고 온 데이터보다 크다면 지우기
                while(!q.isEmpty() && q.getLast().value > now){
                    q.removeLast();
                }
                q.addLast(new Node(i, now));

                // 범위를 벗어났다면, 앞에 데이터 제거
                if(q.getFirst().index <= i-L){ // 범위를 벗어났다면,
                    q.removeFirst();
                }

                bw.write(q.getFirst().value + " ");
            }

            bw.flush();
            bw.close();
        } catch (Exception e) {
            System.out.println(e);
        }
    }

    static class Node{
        int index;
        long value;

        Node(int index, long value){
            this.index = index;
            this.value = value;
        }
    }

    static long longData(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
}