Simple, fast Java solution WITHOUT deque, beat 98.3% submissions


  • 0
    D

    Here is a solution that only uses two pointers, one for start index of the window, the other for the index of the max element. It's faster than 98.3% Java submissions.

     public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];
        if(nums.length==0) return new int[0];
        int end=0, maxIndex=0, index=0;
        
        while(end<nums.length){
            if(end-maxIndex>=k){//previous max value expires
                maxIndex++;
                for(int i=maxIndex+1; i<=end; i++){
                    if(nums[i]>nums[maxIndex])  maxIndex=i;
                }
            }else{
                if(nums[end]>nums[maxIndex]){
                    maxIndex=end;
                }
            }
            if(end>=k-1){
                res[index++]=nums[maxIndex]; 
            }
            end++;
        }
        
        return res;

Log in to reply
 

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