<Hard> Sliding Window Maximum (LeetCode : C#)

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

📕 문제 설명

정수 배열과 sliding window 크기 주어질 때 각 슬라이딩 윈도우에 대한 max를 담은 배열 반환

• Input
  정수 배열, sliding window 크기
• Output
  max sliding window (int[])

예제

풀이

우선 순위 큐를 활용해서 구현

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) 
    {
        var queue = new PriorityQueue<int, int>(); // element, priority
        var result = new int[nums.Length - k + 1];

        for (int i = 0; i < nums.Length; i++)
        {
            // 현재 window안에 있는 index가 아닌데 max값이면 빼기
            while (queue.Count > 0 && i - k >= queue.Peek()) 
            {
                queue.Dequeue(); 
            }

            queue.Enqueue(i, -nums[i]); // 최대 뽑기 위해 - 붙임 

            if (i >= k - 1) // 현재 window에서의 최대값 
            {
                result[i - (k - 1)] = nums[queue.Peek()];
            }
        }

        return result;
    }
}

결과