# Sliding Window Maximum ### Source - leetcode: [Sliding Window Maximum | LeetCode OJ](https://leetcode.com/problems/sliding-window-maximum/) - lintcode: [(362) Sliding Window Maximum](http://www.lintcode.com/en/problem/sliding-window-maximum/) ~~~ 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; Challenge o(n) time and O(k) memory ~~~ ### 題解 O(nk)O(nk)O(nk) 的時間復雜度的方法很容易想到，不停地從當前窗口中取最大就好了。但其實可以發現下一個窗口的最大值與當前窗口的最大值其實是有一定關系的，但這個關系不是簡單的將前一個窗口的最大值傳遞給下一個窗口，**因為數組中每一個元素都是有其作用范圍的，超過窗口長度后就失效了！**所以現在思路就稍微清晰一些了，將前一個窗口的最大值傳遞給下一個窗口時需要判斷當前遍歷的元素下標和前一個窗口的最大元素下標之差是否已經超過一個窗口長度。 問題來了，思路基本定型，現在就是選用合適的數據結構了。根據上面的思路，這種數據結構應該能在 O(1)O(1)O(1) 的時間內返回最大值，且存儲的元素最大可以不超過窗口長度。常規一點的可以采用隊列，但是此題中使用普通隊列似乎還是很難實現，因為要在 O(1)O(1)O(1) 的時間內返回最大值。符合這個要求的數據結構必須能支持從兩端對隊列元素進行維護，其中一種實現方法為隊首維護最大值，隊尾用于插入新元素。雙端隊列無疑了，有關雙端隊列的科普見 [雙端隊列](https://zh.wikipedia.org/wiki/%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97)。可以自己試著以一個實際例子來幫助理解。 ### Java ~~~ public class Solution { /** * @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> winMax = new ArrayList<Integer>(); if (nums == null || nums.length == 0 || k <= 0) return winMax; int len = nums.length; Deque<Integer> deque = new ArrayDeque<Integer>(); for (int i = 0; i < len; i++) { // remove the smaller in the rear of queue while ((!deque.isEmpty()) && (nums[i] > deque.peekLast())) { deque.pollLast(); } // push element in the rear of queue deque.offer(nums[i]); // remove invalid max if (i + 1 > k && deque.peekFirst() == nums[i - k]) { deque.pollFirst(); } // add max in current window if (i + 1 >= k) { winMax.add(deque.peekFirst()); } } return winMax; } } ~~~ ### 源碼分析 1. 移除隊尾元素時首先判斷是否為空，因為在移除過程中可能會將隊列元素清空。 1. 在移除隊尾元素時`nums[i] > deque.peekLast()`不可取等于號，因為這樣會將相等的元素全部移除，這樣會在窗口中部分元素相等時錯誤地移除本該添加到最終結果的元素。 1. 移除失效元素和添加元素到最終結果時需要注意下標`i`和`k`的關系，建議舉例確定。 ### 復雜度分析 時間復雜度 O(n)O(n)O(n), 空間復雜度 O(k)O(k)O(k). 空間復雜度可能不是那么直觀，可以這么理解，雙端隊列中的元素最多只能存活 k 次，因為只有最大元素的存活時間最久，而最大元素在超過窗口長度時即被移除，故空間復雜度為 O(k)O(k)O(k). ### Reference - 《劍指 Offer》 - [sliding-window-maximum 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/sliding-window-maximum/) - [Maximum of all subarrays of size k (Added a O(n) method) - GeeksforGeeks](http://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/)