Sliding Window Maximum

Question

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Example

For array [1, 2, 7, 7, 8], moving window size k = 3. return [7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8] , return the maximum 7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum 7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum 8;

Example 2

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

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Note: You may assume _k _is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Challenge

o(n) time and O(k) memory

Tags

LintCode Copyright Deque Zenefits

Related Problems

Hard Sliding Window Matrix Maximum 35 % Hard Paint House II 28 % Hard Sliding Window Median

Analysis

Deque

开始想到用一个固定大小的Max Heap，但是由于Heap的删除操作比较麻烦，最好使用HashHeap，不过HashHeap在Java中并没有现成的implementation，而其实现十分繁琐，因此转而思考有没有别的数据结构。相比Sliding Window Median，这里寻找Maximum也许更容易一些，因为是一个局部极值，也许可以用stack或者queue来记录当前窗口的最大元素？但是单纯使用stack或者queue都不能很好地满足需要，因为想维护一个数据结构，能够保持其元素的单调递减性，其头部永远是当前window的maximum，如果有新的较大元素，则将该结构内比它小的元素都pop出来，再push新的较大元素。Java中恰好有这样一个数据结构：Deque，也就是double-ended-queue，“双端队列”之意，其中一个实现为ArrayDeque （参考：https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html），能够满足两端的offer, poll, peek操作。也可以直接用LinkedList实现。

对于example:

nums = [1, 2, 7, 7, 8]

k = 3

先将k-1个元素填入，

| 2 |

从kth元素开始，再依次加入新元素并且删除原有旧元素，保持sliding window的大小不变

Window:
[|1, 2, 7|, 7, 8]

Deque:
| 7 |

Output: [7]

Window:
[1, |2, 7, 7|, 8]

Deque:
| 7, 7 |

Output: [7, 7]

Window:
[1, 2, |7, 7, 8|]

Deque:
| 8 |

Output: [7, 7, 8]

对于每一个nums中的元素都只扫描一遍，在deque中的操作时间复杂度也是在O(k)数量级以下，因此总时间复杂度为O(n * k) ~ O(n)，空闲复杂度O(k)，用于维护一个Deque。

We scan the array from 0 to n-1, keep "promising" elements in the deque. The algorithm is amortized O(n) as each element is put and polled once.

At each i, we keep "promising" elements, which are potentially max number in window [i-(k-1),i] or any subsequent window. This means

1. If an element in the deque and it is out of i-(k-1), we discard them. We just need to poll from the head, as we are using a deque and elements are ordered as the sequence in the array

2. Now only those elements within [i-(k-1),i] are in the deque. We then discard elements smaller than a[i] from the tail. This is because if a[x] <a[i] and x<i, then a[x] has no chance to be the "max" in [i-(k-1),i], or any other subsequent window: a[i] would always be a better candidate.

3. As a result elements in the deque are ordered in both sequence in array and their value. At each step the head of the deque is the max element in [i-(k-1),i]

记录max index

每次循环在sliding window里找到maximum对应的index，在下一次循环中根据新加入window的元素大小以及更新这个index，可以达到O(1) space, O(n) time的算法。

Monotonic Queue

也有大神解读为monotonic queue problem https://leetcode.com/problems/sliding-window-maximum/discuss/65885/This-is-a-typical-monotonic-queue-problem

Solution

Deque - Storing Value in Deque

public class Solution {
    // Make sure the maximum number is at the head of the deque
    public void inQueue(Deque<Integer> deque, int num) {
        while (!deque.isEmpty() && deque.peekLast() < num) {
            deque.pollLast();
        }
        deque.offerLast(num);
    }

    // Remove the previous numbers for sliding window constraints
    public void outQueue(Deque<Integer> deque, int num) {
        if (deque.peekFist() == num) {
            deque.pollFist();
        }
    }
    /**
     * @param nums: A list of integers.
     * @return: The maximum number inside the window at each moving.
     */
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        Deque<Integer> deque = new ArrayDeque<Integer>();

        if (nums == null || nums.length == 0) {
            return ans;
        }

        // Initialize the deque with first k - 1 element
        for (int i = 0; i < k - 1; i++) {
            inQueue(deque, nums[i]);
        }

        // Continue from k-th element, for the maximum in each sliding window
        for (int i = k - 1; i < nums.length; i++) {
            inQueue(deque, nums[i]);
            ans.add(deque.peekFirst());
            outQueue(deque, nums[i - k + 1]);
        }
    }
}

*Deque - Storing Index in Deque - Monotonic Queue (17ms 51.07% AC)

The dq head always stores the index of maximum in the sliding window

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0 || n == 1 || k == 1) {
            return nums;
        }
        int[] result = new int[n - k + 1];
        // Store index
        LinkedList<Integer> dq = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // remove index out of sliding window [i - k + 1, i]
            if (!dq.isEmpty() && dq.peek() < i - k + 1) {
                dq.poll();
            }
            // remove numbers in deque which are smaller than the new element nums[i] in the sliding window
            while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
                dq.pollLast();
            }
            dq.offer(i);
            if (i - k + 1 >= 0) {
                result[i - k + 1] = nums[dq.peek()];
            }
        }
        return result;
    }
}

Alternative Approach 1 - Time O(n) Space O(1) (1ms AC)

max_index - the index of maximum in current (or previous if in next loop) sliding window

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int size = nums.length;
        if( nums.length == 0 || k == 0 || k > nums.length)
            return new int[0];

        int[] max_window = new int[size-k+1];
        int max =0;
        int max_index =-1;
        int index=0;

        for(int j =0;j<size-k+1;j++)
        {
            if(j>max_index)
            {
                max_index = j;
               for(int m =j;m<j+k;++m)
               {
                   if(nums[m]>= nums[max_index])
                       max_index=m;
               }        

            }
            else
            {
                if(nums[j+k-1] > nums[max_index])
                    max_index=  j+k-1;

            }

            max_window[index++] = nums[max_index];

        }
        return max_window;
    }
}

Alternative Approach 2 - Two max arrays - Time O(n) Space O(n) - (4ms AC)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || nums.length == 1)
            return nums;

        int[] max_left = new int[nums.length]; // max from the left
        int[] max_right = new int[nums.length]; // max from the right

        int n = nums.length;

        // initialize starting points for left and right
        max_left[0] = nums[0]; // max for first value from the left is just first val in nums
        max_right[n - 1] = nums[n - 1]; // max for last value is last val since we start here

        // partition array into windows of size k
        for (int i = 1; i < n; i++)
        {
            // see if this is the first number in the partition, if so then the max is 
            // the value at that index in nums, otherwise you get max between the previous
            // max value and current value in nums
            // go through each number in the partition and update the max for the numbers
            // up to that index in the partition, in the end the last number in partition
            // will have the max for this partition
            max_left[i] = (i % k) == 0 ? nums[i] : Math.max(max_left[i - 1], nums[i]);

            // get index for right side
            int j = n - i - 1;
            // do the same thing as max_left, but for the right side so we are going
            // from right to left
            max_right[j] = (j % k == 0) ? nums[j] : Math.max(max_right[j + 1], nums[j]);
        }

        // there are n - k + 1 sliding windows, since we start from 0, 1, 2,...until n - k
        // so going from index 0 to n-k, total is n - k + 1 windows
        int[] sliding_max = new int[n - k + 1];

        for (int i = 0; i < sliding_max.length; i++)
        {
            // max is either value at index i in max_right, or the last value in this
            // sliding window for max_left, since we went from left to right for that
            // so max is the last one in the sliding window
            sliding_max[i] = Math.max(max_right[i], max_left[i + k - 1]);
        }
        return sliding_max;
    }
}

Reference

• LeetCode Articles:

• LeetCode Discussion: Java O(n) solution using deque with explanation

• Java Doc: ArrayDeque

• Tutorialspoint: Java ArrayDeque

• [GeeksforGeeks: Sliding Window Maximum](https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/\

• https://leetcode.com/problems/sliding-window-maximum/discuss/65885/This-is-a-typical-monotonic-queue-problem