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


  • 0
    Z

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

  • 0
    M

    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


Log in to reply
 

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