LeetCode 23.08.16 : Sliding Window Maximum

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

 

풀이

- 보자마자 이중 for문? 생각했지만 제한조건에 nums.length가 10의 5승인 걸 보고 그만둠.

- 우선순위 큐로 최초 k 사이즈만큼의 num들을 정렬해놓고, 다음 k + index에 위치한 숫자를 EnQueue하는 방식으로 생각.

- 우선순위 큐 검색 도중 window 안에 들어와있는 값이 아니면 삭제해보도록 하자.

- 닷넷에는 이미 구현된 PriorityQueue가 있다.

 

public class IntMaxCompare : IComparer<int>
{
	public int Compare(int x, int y) => y.CompareTo(x);
}
        
static int[] Solution(int[] nums, int k)
{
	if (k == 1)
		return nums;
            
	var result = new int[nums.Length - k + 1];

	var queue = new PriorityQueue<int, int>(new IntMaxCompare());
	for (int i = 0; i < k; i++)
		queue.Enqueue(i, nums[i]);

	for (int i = k; i <= nums.Length; i++)
 	{
		int maxIdx = queue.Peek();
		while (maxIdx <= i - k - 1)
		{
  			queue.Dequeue();
			maxIdx = queue.Peek();
		}
                
		result[i - k] = nums[maxIdx];
                
		if(i == nums.Length)
			break;
                
		queue.Enqueue(i, nums[i]);
	}

	return result;
}

 

결과

Runtime 436 ms (상위 40.53%)

Memory 61.8 MB (상위 32.54%)

 

 

피드백

첫 개시 일일 문제가 Hard 난이도라서 당황했는데, 안정적으로 금방 해결해서 다행인 듯.

PriorityQueue 지원 때문에 .Net 7.0 SDK를 설치하느라 괜히 더 걸렸다 (...)