Java solution with O(n)


  • 0
    L

    The basic idea to solve this problem is to keep the data into a queue as the poll and add are O(1) operations. However, the tricky part is the find the max in the constant operation. This solution uses amortized O(1) for finding max value by maintaining a deque that will contain the max seen just now because as a queue, the last seen max is the the actual max.

    public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length==0) {
                return new int[0];
            }
            
            int[] window = new int[nums.length-k+1];
            int count=0;
            queuewithmax queue = new queuewithmax();
            for(int i=0;i<nums.length;i++) {
                queue.add(nums[i]);
                if(queue.size()==k) {
                    window[count++] = queue.getMax();
                    queue.poll();
                }
            }
            return window;
        }
        
        private class queuewithmax {
            private Queue<Integer> queue = new LinkedList<>();
            private Deque<Integer> deque = new LinkedList<>();
            
            public int getMax() {
                return deque.peek();    
            }
            
            public void add(int i) {
                queue.add(i);
                if(deque.isEmpty()) {
                    deque.addFirst(i);
                    return;
                }
                while(!deque.isEmpty() && deque.peekLast() < i) {
                    deque.removeLast();
                }
                deque.addLast(i);
            }
            
            public int poll() {
                int val = queue.poll();
                if(val==deque.peekFirst()) {
                    deque.pollFirst();
                }
                return val;
            }
            
            public int size() {
                return queue.size();
            }
        }
    

Log in to reply
 

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