Java O(n) easy to understand solution


  • 0
    J

    maxId always point to the max value in the current window. If it drops out of current window of k, recalculate.

    public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || k <= 0) return new int[0];
            
            int n = nums.length;
            int maxId = findMax(nums, 0, k);
            int[] result = new int[n - k + 1];
            int ridx = 0;
            result[ridx] = nums[maxId];
            for (int i = k; i < n; i++) {
                if (maxId < i - k + 1) {
                    maxId = findMax(nums, i - k + 1, i);
                }
                if (nums[i] >= nums[maxId]) {
                    maxId = i;
                }
                ridx++;
                result[ridx] = nums[maxId];
            }
            return result;
        }
        
        private int findMax(int[] nums, int start, int end) {
            int maxId = start;
            for (int j = start; j < end; j++) {
                if (nums[j] > nums[maxId]) {
                    maxId = j;
                }
            }
            return maxId;
        }
    

Log in to reply
 

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