# This real linear time simple java solution beats 97% solution

• ``````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;
}
``````

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

• 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.

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

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