This real linear time simple java solution beats 97% solution


  • 0
    A
    public static int[] maxSlidingWindow(int[] nums, int k) {
            if( nums == null || nums.length == 0 ) return new int[]{};
    		if ( k == 1 ) return nums;
    		
    		int left = 0 , right = 0 , i = 0 , maxIndex = -1 , ri = 0;
    		int loop = nums.length;
    		int curMax = Integer.MIN_VALUE;
    		int[] res = new int[loop - k +1];
    		while( (left + k) <= loop ){
    			right = left + k;
    			//the current max value index is out of range.
    			if ( maxIndex < left) {
    				curMax = Integer.MIN_VALUE;
    				for( i = left ; i < right ; i++ ){
    					curMax = Math.max(nums[i], curMax);
    					maxIndex = curMax == nums[i] ? i : maxIndex;
    				}
    				
    				res[ri++] = curMax;
    			}else{
    				curMax = Math.max(curMax, nums[right - 1]);
    				res[ri++] = curMax;
    			}
    			left++;
    		}
            return res;
        }
    

  • 1

    What do you mean with "real" linear time? Are there any solutions that claim to be but aren't?


  • 1

    Ah, it's just another solution advertised as being especially good but actually being especially bad. It's not linear time but only O(n2). Consider cases like nums = [70000, 69999, ..., 2, 1] and k = 35000. The previous max value always drops out and thus you always scan the entire window. That case btw takes you way over a second and gets you Time Limit Exceeded.


  • 0
    T

    Agreed, if the input int[] is sorted in descending order, this solution is the worst solution


Log in to reply
 

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