# 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](https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html%EF%BC%89%EF%BC%8C%E8%83%BD%E5%A4%9F%E6%BB%A1%E8%B6%B3%E4%B8%A4%E7%AB%AF%E7%9A%84offer), 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] \ 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\ ## Solution ### Deque - Storing Value in Deque ```java public class Solution { // Make sure the maximum number is at the head of the deque public void inQueue(Deque 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 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 maxSlidingWindow(int[] nums, int k) { ArrayList ans = new ArrayList(); Deque deque = new ArrayDeque(); 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 ```java 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 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 ```java 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;jmax_index) { max_index = j; for(int m =j;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) ```java 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: ](http://articles.leetcode.com/sliding-window-maximum/) * [LeetCode Discussion: Java O(n) solution using deque with explanation](https://discuss.leetcode.com/topic/19055/java-o-n-solution-using-deque-with-explanation) * [Java Doc: ArrayDeque](https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html) * [Tutorialspoint: Java ArrayDeque](http://www.tutorialspoint.com/java/util/java_util_arraydeque.htm) * \[GeeksforGeeks: Sliding Window Maximum]\([https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/\\](https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/\)/) *