Accepted 5ms Java solution with explanation


  • 0
    L
    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || nums.length == 0) return new int[]{};
            int[] res = new int[nums.length-k+1];
            
            // get the max for the first window
            int max = getMax(nums, 0, k-1);
            res[0] = max;
            
            /* Simply, we just need to compare the newly-added element(newElement) with the max   in the last window 
             * if newElement > max, the max in the current window must be this newElement i.e the rightmost element in the current window
             * else newElement <= max, the max in the current window is still the same as that in the last window
             * However, there is a special case that what if the max in the last window is in the leftmost position? in that case,
             * the max would be out of the window, when the window moves, so the previous logic would not hold.
             * We need to consider this special case. See the code.
             */
            
            for (int i = 1; i < nums.length-k+1; i++) {
                int newElement = nums[i+k-1];
                if (max == nums[i-1]) {
                    // special case: if the max in the last window in the leftmost position
                    if (newElement < max) max = getMax(nums, i, i+k-1);    // Iterate through the array again to find the max
                    else max = newElement;
                } else {
                    // general case
                    max = Math.max(max, newElement);
                }
                res[i] = max;
            }
            return res;
        }
        
        private int getMax(int[] nums, int start, int end) {
            int max = nums[start];
            for (int i = start+1; i <= end; i++) {
                if (max < nums[i]) max = nums[i];
            }
            return max;
        }
    }
    

Log in to reply
 

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