[leetcode] [239] Sliding Window Maximum

문제 : leetcode.com/problems/sliding-window-maximum/

---

정수배열 nums 이 주어지고 슬라이딩 윈도우 크기 k가 주어진다.

배열의 맨 왼쪽부터 k개를 유지하면서 오른쪽으로 탐색하는 슬라이딩 윈도우가 있을 때 슬라이딩 윈도우가 오른쪽으로 한 칸 씩 이동할때마다 해당 슬라이딩 윈도우에 있는 요소들 중 가장 큰 값을 가지는 숫자를 배열에 저장해서 반환하라.

---

우선순위 큐에 요소들을 저장한다.

이 때, nums 요소와 인덱스를 같이 저장한다. 우선순위는 nums 요소(정수)로 판단한다. 

만약 탐색 시 탐색 중인 nums 인덱스가 k이상일 때, 우선순위 큐를 탐색하면서 큐의 top에 있는 인덱스 정보를 현재 탐색 중인 인덱스와 비교한다.

큐의 top에 있는 인덱스 정보와 현재 탐색 중인 nums 인덱스의 차가 k 이상이라면 큐의 top에 있는 값은 슬라이딩 윈도우에 있을 수 없으므로 pop한다. 

이 과정을 top에 있는 값이 슬라이딩 윈도우에 있는 값일때까지 pop 한다.

유효한 값만 큐에 있게 되었을 때 큐의 top에 있는 값이 현재 슬라이딩 윈도우의 최대값이 되므로 정답 배열에 추가한다.

모든 nums 배열을 탐색했을 때 구한 정답 배열이 정답이다.

 

N을 nums 요소 개수, M을 k라 하면 시간복잡도는 O(NlogM).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/239.%20Sliding%20Window%20Maximum.cpp