[리트코드] sliding-window-maximum (슬라이딩 윈도우) <Java>

https://leetcode.com/problems/sliding-window-maximum/

Sliding Window Maximum - LeetCode

 

 

 

풀이

---

해당 문제는 구간의 최댓값의 리스트를 반환하는 것이다.

 

예를들면

nums = [ 1, 2, 3, 4, 2,]

k = 2

 

일 때,

answer = [2, 3, 4, 4]

를 반환하면 된다.

 

Sliding Window(슬라이딩 윈도우) 알고리즘을 활용하여 문제를 풀었다.

다른 어려운 알고리즘이 아닌 두포인터 + 우선순위 큐 를 이용하면 되는 문제다.

 

구간의 값을 우선순위 큐에 넣어준다. 이때 숫자와 인덱스값을 넣어주어 구간안에 존재하는 값인지 확인한다.

static class Number implements Comparable<Number>{
    	
    	int index, num;
    	
    	Number(int index, int num){
    		this.index = index;
    		this.num = num;
    	}

		@Override
		public int compareTo(Number number) {
			return this.num - number.num;
		}
    }

클래스는 다음과 같이 선언하여 풀었다.

 

해당 숫자가 구간안에 존재하는지 확인하고 구간안에 존재하는 수가 나올 때까지 PriorityQueue를 pop 해준다.

while(pq.peek().index <= i - k) {
	pq.poll();
}

 

<두포인터 + 우선순위 큐 풀이>

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<Number> pq = new PriorityQueue<>();
    	List<Integer> result = new ArrayList<>();
    	
    	for(int i = 0 ; i < nums.length ; i++) {
    		
    		pq.add(new Number(i, nums[i]));
    		
    		if(i - k + 1< 0) { continue; }    		
    		while(pq.peek().index <= i - k) {
    			pq.poll();
    		}
    		
    		result.add(pq.peek().num);
    	}
    	
    	int[] answer = new int[result.size()];
    	
    	int index = 0;
    	for(int num : result) {
    		answer[index++] = num;
    	}
    	
    	return answer;
    }
    static class Number implements Comparable<Number>{
    	
    	int index, num;
    	
    	Number(int index, int num){
    		this.index = index;
    		this.num = num;
    	}

		@Override
		public int compareTo(Number number) {
			return number.num - this.num;
		}
    }
}

 

 

같은 슬라이딩 윈도우지만, 더 빠르게 푸는 방식이 있어서 가져왔다.

데큐의 성질을 이용해 푼 것이다.

 

인덱스에 해당하는 수 중 가장 작은 수를 왼쪽에 넣는다.

 

알고리즘 순서

1. 가장 왼쪽의 수가 인덱스 범위 안에 있는 수인지 확인한다. 범위 안에 있을 때까지 pop 한다.
2. 현재 인덱스 수가 가장 뒤의 수보다 크면 하나씩 빼고 자신보다 큰 수가 있기전까지 오른쪽 끝을 pop 한다.
3. 현재 인덱스 수를 가장 오른쪽에 넣어준다.

 

<Deqeu 를 이용한 풀이>

import java.util.*;

class Solution {
    static int[] maxTree, list;
    
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] answer = new int[nums.length - k  + 1];
        
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = 0 ; i < nums.length ; i++){
            if(!dq.isEmpty() && i - dq.peekFirst() >= k){
                dq.pollFirst();
            }
            
            while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
                dq.pollLast();
            }
            dq.offerLast(i);
            if (i - k + 1>= 0) {
                answer[i - k + 1] = nums[dq.peekFirst()];
            }
        }
    	return answer;
    }
}