Leetcode 239) Sliding Window Maximum

27 May 2021 in Algorithms

• max 값뿐 아니라, max ind 값을 추적한거 잘했다. 왜냐면, 중복되는 수가 엄청 많이 나왔을 때, max가 가장 나중의 값에 있다면

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length-k+1];
        if(k==1){
            return nums;
        }
        if(k>=nums.length){
            int max= nums[0];
            for(int i =1;i<nums.length;i++){
                if(max<=nums[i]){
                    max=nums[i];
                }
            }
            result[0]=max;
            return result;
        }
        //k가 더 작을 시, 맨첨 값에서 max만 구해주고 그 다음에는 sliding window로 추가되는 원소와 그 전 max와 비교해서 어레이에 넣어준다.
        int max= nums[0];
        int max_ind=0;
        for(int i =0;i<k;i++){
            if(max<=nums[i]){
                max=nums[i];
                max_ind=i;
            }
        }

        result[0]=max;
        for(int i=k;i<nums.length;i++){
            if(i-k<max_ind){
                if(nums[i]>=max){
                    max_ind=i;
                    max=nums[i];
                }
            }else{
                int j=max_ind+1;
                max=nums[j];

                int upper= max_ind+k;

                while(j<=upper && j<nums.length){
                    if(max<=nums[j]){
                        max_ind=j;
                        max=nums[j];
                    }
                    j++;
                }
            } 
            result[i-k+1]=max; 
        }
        return result;
    }
}

다른 풀이

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        
        int[] q = new int[nums.length];
        int[] p = new int[nums.length];
        int head = 0, tail = -1;
        for(int i = 0; i < nums.length; i++) {
            while(head <= tail && q[tail] <= nums[i]) {
                tail--;
            }
            q[++tail] = nums[i];
            p[tail] = i;
            while(p[head] <= i - k) {
                head++;
            }
            if(i - k + 1 >= 0) ans[i - k + 1] = q[head];
        }
        return ans;
    }
}

• queue를 사용해서 풀기도 했다.

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n-k+1];
        Deque<Integer> q = new LinkedList<Integer>();
        int i;
        for(i=0;i<k;i++){
            while((!q.isEmpty()) && (nums[i] > nums[q.peekLast()])){
                q.removeLast();
            }
            q.addLast(i);
        }
        int l=0;
        for(;i<n;i++){
            ans[l++] = nums[q.peek()];
            while((!q.isEmpty()) && i-k >= q.peek()){
                q.removeFirst();
            }
             while((!q.isEmpty()) && (nums[i] > nums[q.peekLast()])){
                q.removeLast();
            }
            q.addLast(i);
        }
        ans[l++] = nums[q.peek()];
        return ans;
    }

#

오답 노트

이 두 코드의 차이! 아래 코드는 j 범위가 계속 늘어난다. 와 조심해라

int upper= max_ind+k;

while(j<=upper && j<nums.length){
    if(max<=nums[j]){
        max_ind=j;
        max=nums[j];
        System.out.println("max:" +max);
    }
    j++;
}

while(j<=(max_ind+k) && j<nums.length){
    if(max<=nums[j]){
        max_ind=j;
        max=nums[j];
        System.out.println("max:" +max);
    }
    j++;
}

• 논리는 맞는데, while문 안에 for문이 있어서 그런지 끝에 긴 인풋이 들어오면 timeout 된다.
• max_ind 를 추가해서 풀면 아마 time out 에 안 걸릴듯?

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res= new int[nums.length-k+1];
        int max= Integer.MIN_VALUE;
        for(int i=0;i<k;i++){
            if(max<nums[i]){
                max=nums[i];
            }
        }
        int start=0;
        int end=k;
        res[0]=max;

        while(end<nums.length){
            if(nums[start]==max){
                if(nums[end]>=nums[start] ){
                    max=nums[end];
                    max2=Integer.MIN_VALUE;
                }else{
                    max=Math.max(max2,nums[end]);
                    for(int j=start+1;j<=end;j++){
                        if(max<nums[j]){
                            max=nums[j];
                        }
                    }
                }            
            }else{
                max=Math.max(max,nums[end]);
            }
            end++;start++;
            res[start]=max;
        }
        return res;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k){
        int[] res= new int[nums.length-k+1];
        int max= Integer.MIN_VALUE;
        int max_ind =0;
        for(int i=0;i<k;i++){
            if(max<nums[i]){
                max=nums[i];
                max_ind=i;
            }
        }
        res[0]=max;
        int start=1;
        int end=k;
        while(start<nums.length-k+1){
            if(max_ind<start){
                if(nums[end]>=max ){
                    max_ind=end;
                    max=nums[end];
                }else{
                    int j=start;
                    max=nums[j];
                    int upper= start+k;
                    while(j<upper && j<nums.length){
                        if(max<=nums[j]){
                            max=nums[j];
                            max_ind=j;
                        }
                        j++;
                    }
                }            
            }else{
                if(max<=nums[end]){
                    max=nums[end];
                    max_ind=end;
                }
            }
            res[start]=max;
            start++;end++;
        }
        return res;
    }
}