[LeetCode]239. Sliding Window Maximum

Sliding Window Maximum - LeetCode

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

• 풀이방법
  • 일단 이 문제는 FIXED SIZE의 Window를 사용하는 문제이다.
  • 제목 보고 내 마음대로 문제를 유추했었는데.
  • 이 문제는, sliding window를 이동해 감에 따라, window의 각 위치에서 window내의 max값을 추출하는 것이다.
  • 하나를 빼고, 하나를 추가하여 그 안에서 max값을 찾아야 한다.
  • ?????? 하 이거 은근 어렵다 . 아니 그냥 어렵다 어떻게 하는지 모르겠다.
  • num의 개수가 최대 10만개다. k도 최대 10만개다.
  • Fixed size sliding window의 경우, window 크기가 k에 달하면, window를 움직임에 따라, 맨 첫 번째 수를 제거하고, 맨 뒤에 수를 하나 추가하는 식으로 진행된다.
  • 아 진심 모르겠다 ㅋㅋㅋ 다 시간 초과될만한 것들로만 떠오른다....

시간초과

O(N^2) 일거 알고 이렇게 짰다. 일단 시간 초과 에러라도 봐야지 다른 사람들 풀이를 볼 생각이 들 것 같았다.

• 이건 그냥 20001개 크기의 check array를 생성하여, nums에 있는 각 element를 마주할 때 마다 check array에서 해당 element에 해당하는 index의 값을 1씩 증가시킨다. 그리고 k에 달할 경우, check에서 0보다 큰 index들을 PQ에다가 넣어서 pq에서 max를 추출한다 . 이 때 PQ에는 같은 값이 중복해서 들어가지 않게 한다.
• window를 이동시키면서, check에서 해당 값을 1 감소시킨다. 감소시킨 결과가 0이라면, PQ에서도 해당 값을 제거 시켜야 한다.
• PQ에서 remove(Object o)는 O(n)이 걸리는데 outer loop 까지 있으니 O(n^2)이 나올 수 밖에 없다 ㅋㅋ..

public static int[] maxSlidingWindow(int[] nums, int k){
        int length=0;
        int[] check = new int[20001];
        Queue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        ArrayList < Integer > res = new ArrayList<Integer>();
        int[] resArr;
        if(nums.length<=k){
            Arrays.sort(nums);
            res.add(nums[nums.length-1]);
        } else{
            for(int end=0;end<nums.length;end++){
                check[nums[end]+10000]++;
                if(check[nums[end]+10000]>1);
                else {
                    //System.out.println("CHECK["+nums[end]+"] : "+check[nums[end]+10000]);
                    q.add(nums[end]);
                }
                length++;
                // window 사이즈가 k일 때 마다
                if(length==k){
                    // 현재의 max값을 res에 넣는다.
                    //System.out.println("END : +"+ end +", QUEUE PEEK : "+q.peek());
                    res.add(q.peek());
                    // 맨 앞 element를 제거한다.
                    int del = nums[end-k+1];
                    check[del+10000]--;
                    if(check[del+10000]==0) {
                        //System.out.println("QUEUE REMOVE : "+del);
                        q.remove(del);
                    }
                    length--;
                }
            }
        }
        resArr = new int[res.size()];
        for(int i=0;i< resArr.length;i++){

            resArr[i] = res.get(i);
        }
        return resArr;

    }

Next greater element를 활용 했다는 풀이가 많이 보였다.

• NGE가 뭔지 몰라서 NGE를 먼저 공부해봤다.

  Next Greater Element

Stack말고 deque사용해야할것 같았다.

NGE 처럼, top과만 비교하다가 , top보다 큰게 나타나면 Stack안의 나머지것들과 모두 비교하고

아 이건 deque를 사용해야한다. Sliding Window 특성 상 앞에 것을 하나씩 제거해나가야하기도 하기 때문이다. (물론 NGE를 사용한다면, 무조건 제거되는 경우는 없을 수도 있다 )

• 즉 NGE 처럼 하기는 하는데 , Deque를 사용해서, 무조건 먼저 들어온애를 제거해 줄수도 있어야 한다.

• 그리고, int[] 로 return해야한다는 것.

• 기존의 max가 삭제 되었을 때, 다음 max를 찾기 위해 "Search"를 한다고 생각하면 이 문제는 시간 초과가 걸리게 된다.

  • NGE 를 어떻게 했었는지 생각해 보자
    • Stack에다가 첫 번째 원소를 넣어둔다.
    • 그 다음 원소부터 next라고 칭한다.
    • 현재 next가 stack의 top과 비교 해서, 더 작은 경우, Stack에 push한다.
    • 현재 next가 stack의 top과 비교 해서, 더 큰 경우, Stack의 top을 pop한다.
      • Stack의 top이 현재의 next보다 더 큰게 나올 때 까지 Stack의 element를 pop한다
      • 마지막엔 현재 next를 stack에 push한다.

이 문제는 Sliding Window이기 때문에 Stack대신 Deque를 사용해야 한다. window를 이동할 때 , Stack으로 치자면 가장 아래에 쌓여있는 것을 빼내야 하기 때문이다. 하지만 Stack은 먼저 들어온 것을 빼낼 수 없다. Queue로 치자면, STack처럼 pop도 할 수 있어야 한다. 따라서 Deque를 사용해야 하는 것.

이문제는 NGE의 변형으로 볼 수 있는 것은 window를 sliding 시키면서 각 window에서의 max를 추출해 낸다는 것은, 각 원소의 우측으로 k개 내에서 가장 큰 값을 찾는 것과 같기 때문이다.

• i >k 부터 ,

  • Deque의 맨 앞에 있는 값이, 삭제하는 값과 같은지 확인 한다. —> 삭제 하는 값과 같은 경우 —> 디큐한다.
  • i가 top과 비교해서 더 작거나 같은 경우, Deque에 인큐한다.
  • i가 top과 비교해서 더 큰 경우, 데크의 top을 pop한다.
    • i가 top과 비교해서 더 작거나 같을 때 까지 데크의 top을 pop한다.

• i≤k 일 때 까지 :

  • 현재 i가 stack의 top과 비교해서 더 작거나 같은 경우, 그냥 Deque에 enque 한다.
  • 현재 i가 stack의 top과 비교해서 더 큰 경우, 데크의 top 을 pop한다.
    • i가 top과 비교해서 더 작거나 같을 때 까지 데크의 top을 pop한다.

• 규칙성

  22 20 19 21 19 23 이라면? , k = 6이고

  22 || 20 | 19 이다가 21을 만나면 pop pop 하고 21을 push

  22 || 21 이렇게 되고 그 담엔

  22 || 21 ||19 이다가 23을 만나면 pop pop pop 하고 23을 push

  23

  —> 여기서 나오는 규칙성 : 이 Deque에서는 , top 좌측에는, top보다 작은 수가 올 수 없다. —> 즉, Deque의 First가 Deque에서 가장 큰 수에 해당된다.

public static int[] maxSlidingWindow(int[] nums, int k){
       int[] res = null;
       int curK=0;
       // 먼저, nums의 길이 <=k의 길이인 경우
        ArrayList<Integer> resList = new ArrayList<>();
        if(nums.length<=k){
            Arrays.sort(nums);
            resList.add(nums[nums.length-1]);
        }else {
            Deque<int[]> dq = new LinkedList<>(); // e: {idx, nums[idx]}
            for(int i=0;i<nums.length;i++){
								// 현재 i가 stack의 top과 비교해서 더 큰 경우, 데크의 top 을 pop
                while(dq.isEmpty()==false && dq.getLast()[1]<nums[i]) {
                    dq.removeLast();
                }
								// 현재 수도 Deque에 push한다. 
                dq.addLast(new int[]{i,nums[i]});
                curK++;
								// deque에 들어있는 수를 count한다 
                if(curK == k ){
										// 현재 윈도우에서 max값을 저장한다.
                    resList.add(dq.getFirst()[1]);
                    // 삭제하는것이 dq의 맨 앞 것과 같은지 확인
                    // 만약 현재 index가 3이고, k는 1인 경우면, idx-k+1을 삭제
                    if(dq.getFirst()[0]==i-k+1)dq.removeFirst();
                    curK--;
                }
            }
        }
        res = new int[resList.size()];
        for(int i=0;i<resList.size();i++)
            res[i]=resList.get(i);

       return res;

    }

위의 코드에서 속도를 높이기

위의 코드 그대로면 : JAVA제출자의 35퍼센트 보다만 빠른 속도가 나온다.

• 위의 코드에서 ArrayList가 아닌, 처음부터 int[] res에다 저장하기
  • nums가 4개로 이루어져있고, k가 3이라면 window는 총 두 번이다. 측, int[] res의 길이는 2가 되어야 한다.
  • 이와같이 res의 길이는 미리 알 수가 있다. nums.legnth-k+1이다.

AND

• if(nums.length<=k) 에서 바로 return하기로 바꾸기만 해도

아래와 같이 속도가 향사된다.

public static int[] maxSlidingWindow(int[] nums, int k){
       int cnt=0;
       int curK=0;
       // 먼저, nums의 길이 <=k의 길이인 경우
        int[] res = new int[nums.length-k+1];
        if(nums.length<=k){
            Arrays.sort(nums);
            return new int[]{nums[nums.length-1]};
        }else {
            Deque<int[]> dq = new LinkedList<>(); // e: {idx, nums[idx]}
            for(int i=0;i<nums.length;i++){
                while(dq.isEmpty()==false && dq.getLast()[1]<nums[i]) {
                    dq.removeLast();
                }
                dq.addLast(new int[]{i,nums[i]});
                curK++;
                if(curK == k ){
                    res[cnt++]=dq.getFirst()[1];
                    // 삭제하는것이 dq의 맨 앞 것과 같은지 확인
                    // 만약 현재 index가 3이고, k는 1인 경우면, idx-k+1을 삭제
                    if(dq.getFirst()[0]==i-k+1)dq.removeFirst();
                    curK--;
                }
            }
        }

       return res;

    }