Sliding Window Maximum

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

Sliding Window Maximum - LeetCode

 

주어진 길이의 구간 별 max 값을 배열로 반환 해야 하는 문제이다. 최대 값이 나온 index가 허용하는 범위 내에 새로운 최대 값이 나온다면 해당 값을 기준으로 또 다시 허용하는 구간을 정하면 된다. max 값이 나온 인덱스를 관리 추적하면서 문제를 해결해 주었다. 아래와 같은 코드로 통과하였다.

 

import java.util.*;  
  
public class Solution {  
    public int[] maxSlidingWindow(int[] nums, int k) {  
        int[] answer = new int[nums.length - k + 1];  
  
        int max = 0;  
        int maxIdx = 0;  
        for(int i = 0; i < k; i++){  
            if(nums[i] > max){  
                max = nums[i];  
                maxIdx = i;  
            }  
        }  
  
        int ansIdx = 0;  
        answer[ansIdx++] = max;  
  
        for(int r = k; r < nums.length; r++){  
            int num = nums[r];  
            if(nums[r] >= max){  
                max = nums[r];  
                maxIdx = r;  
            }else if(r - k >= maxIdx){  
                maxIdx = r - k + 1;  
                max = nums[maxIdx];  
                for(int i = maxIdx; i <= r; i++){  
                    if(nums[i] >= max){  
                        max = nums[i];  
                        maxIdx = i;  
                    }  
                }  
            }  
  
            answer[ansIdx++] = max;  
        }  
  
        return answer;  
    }  
}

 

Leetcode의 경우 문제를 통과한 이후 다른 정답들과 비교해서 속도 백분율을 보여준다. 아쉽게도 속도가 나오지 않아 다른 방식들을 확인해보았다. 다른 정답의 경우 Deque 자료구조를 이용해 유효한 max 값을 차례대로 저장해주었다. 아마도 내가 풀이한 방식의 경우 max 값이 버려질 경우 다시 추적해야 하는 방법인데 반해, 해당 방식은 갱신 될 max 값을 미리 저장해서 순회의 효율이 차이 났을 것으로 보인다.