Java Deque O(n) solution


  • 0
    M
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k <= 0) return new int[0];
            int n = nums.length;
            if (k > n) k = n;
            int[] m = new int[n - k + 1];
            int ind = -1;
            Deque<Integer> deq = new ArrayDeque<>();
            for (int i = 0; i < n; ++i) {
                while (!deq.isEmpty() && nums[deq.peekLast()] <= nums[i]) deq.pollLast();
                deq.offerLast(i);
                if (i >= k) {
                    while (!deq.isEmpty() && deq.peekFirst() <= i - k) deq.pollFirst();
                }
                if (i >= k - 1) m[++ind] = nums[deq.peekFirst()];
            }
            return m;
        }
    

Log in to reply
 

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