[Accepted] Java Solution O(nlogn)


  • 0
    P

    The idea is to use Max Heap in the form of a Priority Queue to solve the problem. Insert each element into a Max Heap while removing the old element; thus always maintaining the size of the heap equal to k. Please find the code below:

    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] maxArray = new int[nums.length-k+1];
            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
            
            /**
            * Check for the null case
            **/
            if (nums.length == 0 && nums.length >= k){
                return new int[]{};
            }
            
            for(int i = 0; i < nums.length; i++){
                if(maxHeap.size() < k){
                    maxHeap.add(nums[i]);
                } else {
                    maxArray[i-k] = maxHeap.peek();
                    maxHeap.remove(nums[i-k]);
                    maxHeap.add(nums[i]);
                }
            }
            
            // for the last value
            maxArray[maxArray.length-1] = maxHeap.peek();
            
            return maxArray;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.