My Java approach, beats 97%


  • 0
    J

    My strategy is to just keep the max value in the window. If we advance the window and the previous max value "falls out" of the window, then re-calculate the max of the window.

    It's a little repetitive - I should have split the code to find the max of the k-1 values out into a separate function. But, here goes:

    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (null == nums || nums.length-k+1<0) {
                return null;
            }
            if (k<=1) {
                return nums;
            }
            int[] returnVal = new int[nums.length-k+1];
            
            // Find max of first k-1:
            int max = Integer.MIN_VALUE;
            int i=0;
            while (i<k-1) {
                if (nums[i] > max) {
                    //System.out.println("i=" + i + ", max=" + max);
                    max = nums[i];
                }
                ++i;
            }
            
            while (i<nums.length) {
                //System.out.println("i=" + i + ", max=" + max);
                //System.out.println("Setting returnVal[" + (i-k+1) + "]...");
                returnVal[i-k+1] = max = Math.max(max, nums[i]);
                //System.out.println("returnVal[" + (i-k+1) + "] = " + max);
                // Advancing the window may make the max value fall off
                if (nums[i-k+1] == max) {
                    //System.out.println("Max just fell off...recalculating.");
                    // Set max to max(nums[i-k+1:i])
                    max = Integer.MIN_VALUE;
                    int j=i-k+2;
                    while (j<=i) {
                        //System.out.println("  Considering: " + nums[j]);
                        if (nums[j] > max) {
                            max = nums[j];
                        }
                        ++j;
                    }
                }
                ++i;
            }
            
            
            return returnVal;
        }
    }
    

Log in to reply
 

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