Java using max heap O(n) - Concise easy to understand solution


  • 1
    B

    The problem can be solved by employing a max queue with size k, for each window, remove the left of prev window and add the right of current window, head of the queue will give the current max.

    public int[] maxSlidingWindow(int[] nums, int k) {
            if(null == nums || nums.length == 0){
                return nums;
            }
            
            int[] out = new int[nums.length - k + 1];
            PriorityQueue<Integer> q = new PriorityQueue<Integer>(k,Collections.reverseOrder());
    
            //add 1st window
            for(int i=0;i<k;i++){
                q.add(nums[i]);
            }
            out[0] = q.peek();
            q.remove(nums[0]);
    
            //add remaining windows
            int j = 1,prevEnd = k-1;
            while(j < nums.length - k + 1){
                q.add(nums[prevEnd+1]);
                out[j] = q.peek(); //add the head i.e current max
                q.remove(nums[j]);//remove the current left 
                prevEnd++;
                j++;
            }
            return out;
        }

  • 0
    J

    @bleedcode said in Java using max heap O(n) - Concise easy to understand solution:

    The problem can be solved by employing a max queue with size k, for each window, remove the left of prev window and add the right of current window, head of the queue will give the current max.

    it should be O(nlgn)


Log in to reply
 

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