My O(n) optimized Java solution in 2ms, better than 99.65%

• I based this algorithm on Manacher's algorithm. It is simply based on the fact that every time you move the window, one number is removed and one number is added. So I keep track of the index of the current max number, and if the index of that max is within the bounds of the new window, I only check to see if the newly added number on the right is greater than the current max. Otherwise, a simple for loop to find the new max in the new window.

public int[] maxSlidingWindow(int[] nums, int k) {

``````    if(nums.length == 0) return nums;
int rindex = k-1;
int lindex = 0;
int cmax = nums[0];
int cmaxindex = 0;
int[] ans = new int[nums.length - k + 1];
int u = 0;
while(rindex < nums.length){
if(cmaxindex >= lindex && cmaxindex != 0){
if(nums[rindex] > nums[cmaxindex]){
cmaxindex = rindex;
cmax = nums[cmaxindex];
}
}
else
{   cmax= nums[rindex];
for(int i = lindex; i <= rindex; i++){
if(nums[i] > cmax){
cmax = nums[i];
cmaxindex = i;
}
}
}
ans[u] = cmax;
lindex++;
rindex++;
u++;
}
return ans;
}``````

• This isn't a O(n) solution. You search in the window K times so it's Q(K*n) in worst case.
Also this kinds of code can't be finished in 2ms

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