[LeetCode- Part. 4] 2. 슬라이딩 윈도우 최댓값 ##(+슬라이딩 윈도우, Deque)

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

Sliding Window Maximum - LeetCode

 

 

1. K값에 해당하는 윈도우 초기값 설정

2. 한칸씩 제거하고 추가하는 작업 수행

3. 타임리밋 발생

 

+) 스트림을 이용한 최댓값 구하기

//스트림을 int형으로 매핑 후, 최댓값 찾아서 스트림을 다시 int형으로 변환
Integer maxValue =list.stream()
                    .mapToInt(x -> x)
                    .max().getAsInt();

 

(1) 리스트로 윈도우 만들기

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //정수 배열 nums과 슬라이딩 창 크기 k
        //k창에 해당하는 최댓값 배열을 리턴한다.
        
        
        
        //1.ds
        int n=nums.length;
        int[] result = new int[n-k+1];
        
        if(nums.length==0 || nums==null) return result;
        
        //2.loop
        //하나씩 더하고, 하나씩 뺀다.
        //: 초기값 설정
        ArrayList<Integer> list = new ArrayList<>();
        Integer maxValue=0;
        
        for(int i=0;i<k;i++){
            list.add(nums[i]);
            if(nums[i]>maxValue) maxValue=nums[i];
        }
        result[0]=maxValue;

        for(int i=0; i<n-k; i++){
            list.remove(0);
            list.add(nums[i+k]);
            
            if(maxValue<nums[i+k]) maxValue = nums[i+k];
            else{
                maxValue =list.stream()
                    .mapToInt(x -> x)
                    .max().getAsInt();
            }
            
            result[i+1]=maxValue;
        }
        
        return result;
    }
}

 

(2)큐로 윈도우 만들기

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //정수 배열 nums과 슬라이딩 창 크기 k
        //k창에 해당하는 최댓값 배열을 리턴한다.
        
        
        
        //1.ds
        int n=nums.length;
        int[] result = new int[n-k+1];
        
        if(nums.length==0 || nums==null) return result;
        
        //2.loop
        //하나씩 더하고, 하나씩 뺀다.
        //: 초기값 설정
        Queue<Integer> list = new LinkedList<>();
        Integer maxValue=0;
        
        for(int i=0;i<k;i++){
            list.offer(nums[i]);
            if(nums[i]>maxValue) maxValue=nums[i];
        }
        result[0]=maxValue;

        for(int i=0; i<n-k; i++){
            list.poll();
            list.offer(nums[i+k]);
            
            if(maxValue<nums[i+k]) maxValue = nums[i+k];
            else{
                maxValue =list.stream()
                    .mapToInt(x -> x)
                    .max().getAsInt();
            }
            
            result[i+1]=maxValue;
        }
        
        return result;
    }
}

 

(3) PriorityQueue로 윈도우 만들기

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //정수 배열 nums과 슬라이딩 창 크기 k
        //k창에 해당하는 최댓값 배열을 리턴한다.
        
        
        
        //1.ds
        int n=nums.length;
        int[] result = new int[n-k+1];
        
        if(nums.length==0 || nums==null) return result;
        
        //2.loop
        //하나씩 더하고, 하나씩 뺀다.
        //: 초기값 설정
        Queue<Integer> list = new PriorityQueue<>(Collections.reverseOrder());
        Integer maxValue=0;
        
        int tmp=0;
        for(int i=0;i<k;i++){
            list.offer(nums[i]);
        }
        maxValue=list.poll();
        result[0]=maxValue;
        list.offer(maxValue);

        for(int i=0; i<n-k; i++){
            tmp=nums[i];
            list.remove(tmp);
            list.offer(nums[i+k]);
                        
            result[i+1]=list.poll();
            list.offer(result[i+1]);
        }
        
        return result;
    }
}

 

 

 

--> 타임리밋 발생

---

Queue와 Deque

Queue의 메서드 - offer와 poll

Deque의 메서드 - offerFirst, offerLast / pollFirst, pollLast / peekFirst, peekLast

 

 

문제 구현 순서

(1) Deque 생성

(2) 하나씩 넣으면서 기존 값이 더 크면 pollLast, 새로운 값이 더 크면 pollFirst

 

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //정수 배열 nums과 슬라이딩 창 크기 k
        //k창에 해당하는 최댓값 배열을 리턴한다.
        
        
        
        //1.ds
        int n=nums.length;
        int[] result = new int[n-k+1];
        
        if(k<=0 || nums==null) return result;
        
        //2.loop
        //방의 인덱스 값을 큐에 넣는다.
        //: 초기값 설정 
        Deque<Integer> q = new ArrayDeque<>();
        int index=0;
        
        for(int i=0;i<n;i++){
            
            //(1) 칸의 크기를 유지하면서, 한 칸씩 이동하는 작업
            //1<4-3+1일 경우, 칸 크기가 될 때 까지 뺀다.
            while(!q.isEmpty() && q.peek()<i-k+1) q.poll();
            
            //(2) 기존 값과 비교해 큰 값만 남긴다.
            while(!q.isEmpty() && nums[q.peekLast()]<nums[i]){
                //새로운 값이 더 클 경우 기존 값 제거
                q.pollLast();
            }
            
            //(3) 큐 삽입
            q.offer(i);
            //(4) 결과배열에 대입
            //: 창 크기만큼 이동할 경우, 결과 배열에 추가
            //2>=3-1
            if(i>=k-1) result[index++] =nums[q.peek()];
        }
        
        return result;
    }
}

 

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //정수 배열 nums과 슬라이딩 창 크기 k
        //k창에 해당하는 최댓값 배열을 리턴한다.
        
        
        
        //1.ds
        int n=nums.length;
        int[] result = new int[n-k+1];
        
        if(k<=0 || nums==null) return result;
        
        //2.loop
        //방의 인덱스 값을 큐에 넣는다.
        //: 초기값 설정 
        Deque<Integer> q = new ArrayDeque<>();
        int index=0;
        
        for(int i=0;i<n;i++){
            
            //(1) 칸의 크기를 유지하면서, 한 칸씩 이동하는 작업
            //1<4-3+1일 경우, 칸 크기가 될 때 까지 뺀다.
            while(!q.isEmpty() && q.peek()<i-k+1) q.poll();
            
            //(2) 기존 값과 비교해 큰 값만 남긴다.
            while(!q.isEmpty() && nums[q.peekLast()]<nums[i]){
                //새로운 값이 더 클 경우 기존 값 제거
                q.pollLast();
            }
            
            //(3) 큐 삽입
            q.offer(i);
            //(4) 결과배열에 대입
            //: 창 크기만큼 이동할 경우, 결과 배열에 추가
            //2>=3-1
            if(i>=k-1) result[index++] =nums[q.peek()];
        }
        
        return result;
    }
}

---

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //Deque 이용
        Deque<Integer> dq = new ArrayDeque<>();
        int n=nums.length;
        int[] answer = new int[n-k+1];
        
        int max=Integer.MIN_VALUE;
        //그중 최댓값 비교
        for(int i=0; i<k;i++){
            dq.offerLast(nums[i]);
            for(int x:dq) max=Math.max(x,max);
        }
        answer[0]=max;
        
        
        for(int i=1; i<n-k+1; i++){
            dq.offerLast(nums[i+k-1]);
            dq.pollFirst();
            max=Integer.MIN_VALUE;
            for(int x:dq) max=Math.max(x,max);
            answer[i]=max;
        }
        return answer;
    }
}

->가장 큰 값을 구하는 과정에서 타임리밋 발생

 

문제 해결 과정

#while을 이용해, 인덱스를 통해 칸 크기를 유지하고 가장 큰 값만 남기고 모두 뺀다.

 

(1) 칸의 크기를 유지하면서, 한 칸씩 이동하는 작업

:k 칸 크기가 될 때 까지 뺀다.
            
(2) 기존 값과 비교해 큰 값만 남긴다.
: 새로운 값이 더 클 경우 기존 값 제거

 

(3) 큐 삽입
           
(4) 결과배열에 대입

: 창 크기만큼 이동할 경우, 결과 배열에 추가

 

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque();
        int n=nums.length;
        int[] answer = new int[n-k+1];
        int index=0;
        for(int i=0;i<n;i++){
            //1. K칸 이상 지났는데도 남아있는 경우
            while(!dq.isEmpty() &&dq.peekFirst()<i-k+1){
                dq.pollFirst();
            }
            //2. 새로들어오는 값이 더 큰 경우
            while(!dq.isEmpty() && nums[dq.peekLast()]<nums[i]){
                dq.pollLast();
            }
            
            dq.offer(i);
            
            if(i>=k-1) answer[index++]=nums[dq.peek()];
        }
        return answer;
    }
}