Java Solution using Deque | O(n) Running Time | Refer : https://www.youtube.com/watch?v=ShbRCjvB_yQ&t=128s


  • 0
    M
    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            
            if (nums == null || nums.length == 0) return new int[0];
        
            int size = 0;
            if (k > nums.length) {
                size = 1;
            } else {
                size = nums.length - k + 1;
            }
            
            int[] res = new int[size];
            
            Deque<Integer> maxQ = new LinkedList<Integer>();
            
            int l = 0, r = 0;
            while (r < nums.length) {
                
                while (!maxQ.isEmpty() && nums[r] >= nums[maxQ.peekLast()]) {
                    maxQ.pollLast();
                }
                
                maxQ.offerLast(r);
                
                if (r - l >= k - 1) {
                    res[l] = nums[maxQ.peekFirst()];
                    if (l == maxQ.peekFirst()) maxQ.pollFirst();
                    l++;
                }
                
                r++;
            }
            
            return res;
        }
    }
    

Log in to reply
 

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