# Leetcode 239. Sliding Window Maximum [Hard]

Not so hard for people familiar with streaming processing: You are given an array of integers `nums`, there is a sliding window of size `k`which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

`Input: nums = [1,3,-1,-3,5,3,6,7], k = 3Output: [3,3,5,5,6,7]`

Solution is based on using Deque where we keep only indeces of elements that are max in given window and remove everything smaller on each iteration. Intuitive implementation is:

`class Solution {    public int[] maxSlidingWindow(int[] nums, int k) {        if (nums.length * k == 0) return new int;                int l = 0, r = k-1;        int[] ans = new int[nums.length-k+1];        Deque<Integer> dq = new LinkedList<>(); // keep indeces        // create 1st window        for(int i = l; i <= r; i++) {            // remove what is smaller than index r            while(!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();            dq.offerLast(i);        }                ans = nums[dq.peekFirst()];        l++; r++;        while(r<nums.length) {            // remove the left most element if available            while(!dq.isEmpty() && dq.peekFirst() < l) dq.pollFirst();            // remove what is smaller than index r            while(!dq.isEmpty() && nums[dq.peekLast()] < nums[r]) dq.pollLast();                        dq.offerLast(r);                        ans[l] = nums[dq.peekFirst()];            l++; r++;        }        return ans;    }}`

Each step can be visualized as: [l; r] -> [dequeue for this window]

`[0;2]: [1, 2][1;3]: [1, 2, 3][2;4]: [3;5]: [4, 5][4;6]: [5;7]: `

Java, start-up, hiking, photos, bicycle,journey

## More from Kostya

Java, start-up, hiking, photos, bicycle,journey