[Sliding Window][Hard] 239. Sliding Window Maximum

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

 

Q. nums 배열과 함께 정수 k 가 주어진다. 정수 k 길이 만큼의 window가 있고 이것이 우측 끝까지 이동 할때, 각 window의 최대 값을 찾아라. 

 

 

Solution. 

 window 사이의 수를 확인하며 최대값을 기억한다. 

 그렇게 일단 첫번째 window의 최대값은 얻는다. 

 window를 우측으로 이동 시킨다. 

 값을 추가 했지만, 최대값보단 작다. 그리고 k간격을 유지하기 위해 left를 당겨야 하는데, 이때 위치 정보로 그냥 지우게 되면 다음 최대값을 다시 window loop로 찾아야 한다. (지우는 값이 구간 최대 값이라면, 다음 최대값을 어떻게 찾는가? - 이대로라면 다시 loop를 돌아야 하므로, 이것은 맞지 않다.)

따라서 k 구간의 최대값을 정렬해서 가지고 있어야 한다. 

그러므로, priority queue자료 구조를 사용한다. 

이때 k 간격을 유지키 위해 알아야 할 것은 각 값의 index 정보이다. 즉, 간격외의 값은 무시하는 것이다. 

 

로직을 기반으로 코드를 만들어 본다. 

 

public int[] MaxSlidingWindow(int[] nums, int k) 
{
    // max p-queue.
    PriorityQueue<int, int> pQ = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y - x)); // idx, value.

    int left = 0;
    int right = 0;
    List<int> ret = new List<int>();
    for(; right < nums.Length; ++right) 
    {
        pQ.Enqueue(right, nums[right]);

        int len = right - left + 1;
        if(len == k)
        {
            while(pQ.Count > 0) 
            {
                int index = pQ.Peek();
                if(index < left)
                {
                    pQ.Dequeue();
                    continue;
                }
                ret.Add( nums[index] );
                break;
            }
            ++left;
        }
    }
    return ret.ToArray();
}

 

 

더 최적화의 여지는 충분히 있어 보인다.