Concise Java O(N) solution


  • 0
    J
    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0 || k == 0) return new int[0];
            int[] res = new int[nums.length - k + 1];
            int[] maxes = new int[k]; // maintain maxes numbers
            int front = 0;
            int back = 0;
            int p = 0;
            for (int i = 0; i < nums.length; i++) {
                int n = nums[i];
                if (front != back && maxes[(front + 1) % k] <= i - k) front++; // remove number leaving the window
                while (front != back && n > nums[maxes[back % k]]) back--; // remove smaller numbers
                maxes[(++back) % k] = i;
                if (i >= k - 1) {
                    res[p++] = nums[maxes[(front + 1) % k]];
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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