230207 슬라이딩 윈도우, Sliding Window

시간이나 공간적인 제약이 있는 경우, 데이터 스트림을 효율적으로 처리하기 위한 알고리즘
고정 크기의 윈도우를 이동시켜 각 윈도우의 데이터를 처리하는 방식

• 데이터를 적은 비용으로 처리
• 각 윈도우의 데이터 처리를 유지하는 동시에 메모리 사용량을 최소화 가능

예시

public int findMaxValue(int[] nums, int k) {
    int maxValue = Integer.MIN_VALUE;
    Deque<Integer> deque = new LinkedList<>();
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peek() < i - k + 1) {
            deque.poll();
        }
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offer(i);
        if (i >= k - 1) {
            maxValue = Math.max(maxValue, nums[deque.peek()]);
        }
    }
    return maxValue;
}