Deque, java with explanation


  • 0
    A

    How is given in the hint we can use the deque. We can use it for storing the sliding window elements in descending order. Each time when we are going to add a new element first we remove from tail numbers from deque which are less or equal than the current number. We can remove them because they are never going to be used anywhere as an answer. Also don't forget to remove number which stay on position i-k from the deque. So, it means the answer will be the first element of deque.

    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (k==0) return new int[0];
            ArrayDeque<Integer> q = new ArrayDeque<>();
            int ans[] = new int [nums.length-k+1];
            for (int i=0; i<nums.length; i++) {
                while (!q.isEmpty() && nums[i]>=nums[q.peekLast()]) {
                    q.pollLast();
                }
                if (!q.isEmpty() && q.peekFirst()==i-k) q.pollFirst();
                q.addLast(i);
                if (i-k+1>=0) ans[i-k+1] = nums[q.peekFirst()];
            }
            return ans;
        }
    }
    

Log in to reply
 

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