LeetCode : 239. Sliding Window Maximum

[congr]

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

[congr]

Heap O(NLogK) + removing O(K) => O(NLogK + K)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1]; // [0]
        if (nums.length == 0 || k == 0) return new int[0]; // !!! []

        PriorityQueue<Integer> pq = new PriorityQueue(Collections.reverseOrder());

        for (int i = 0; i < k; i++) pq.add(nums[i]);
        int p = 0;
        res[p++] = pq.peek();

        for (int i = k; i < nums.length ; i++) {
            pq.remove(nums[i-k]); // !!! 
            pq.add(nums[i]);      // !!!
            res[p++] = pq.peek();            
        }

        return res;
    }
}