久久精品中文字幕av,av.涩涩涩涩涩涩涩涩,亚洲国产日韩欧美精品成人久久久,成人福利电影免费在线观看,日产国产原创av,日韩av午夜激情,bt天堂中文字幕,超级碰人妻在线视频,欧美老熟妇久久一区二区

# 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) 的時(shí)間復(fù)雜度的方法很容易想到，不停地從當(dāng)前窗口中取最大就好了。但其實(shí)可以發(fā)現(xiàn)下一個(gè)窗口的最大值與當(dāng)前窗口的最大值其實(shí)是有一定關(guān)系的，但這個(gè)關(guān)系不是簡單的將前一個(gè)窗口的最大值傳遞給下一個(gè)窗口，**因?yàn)閿?shù)組中每一個(gè)元素都是有其作用范圍的，超過窗口長度后就失效了！**所以現(xiàn)在思路就稍微清晰一些了，將前一個(gè)窗口的最大值傳遞給下一個(gè)窗口時(shí)需要判斷當(dāng)前遍歷的元素下標(biāo)和前一個(gè)窗口的最大元素下標(biāo)之差是否已經(jīng)超過一個(gè)窗口長度。 問題來了，思路基本定型，現(xiàn)在就是選用合適的數(shù)據(jù)結(jié)構(gòu)了。根據(jù)上面的思路，這種數(shù)據(jù)結(jié)構(gòu)應(yīng)該能在 O(1)O(1)O(1) 的時(shí)間內(nèi)返回最大值，且存儲(chǔ)的元素最大可以不超過窗口長度。常規(guī)一點(diǎn)的可以采用隊(duì)列，但是此題中使用普通隊(duì)列似乎還是很難實(shí)現(xiàn)，因?yàn)橐?O(1)O(1)O(1) 的時(shí)間內(nèi)返回最大值。符合這個(gè)要求的數(shù)據(jù)結(jié)構(gòu)必須能支持從兩端對(duì)隊(duì)列元素進(jìn)行維護(hù)，其中一種實(shí)現(xiàn)方法為隊(duì)首維護(hù)最大值，隊(duì)尾用于插入新元素。雙端隊(duì)列無疑了，有關(guān)雙端隊(duì)列的科普見 [雙端隊(duì)列](https://zh.wikipedia.org/wiki/%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97)。可以自己試著以一個(gè)實(shí)際例子來幫助理解。 ### 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. 移除隊(duì)尾元素時(shí)首先判斷是否為空，因?yàn)樵谝瞥^程中可能會(huì)將隊(duì)列元素清空。 1. 在移除隊(duì)尾元素時(shí)`nums[i] > deque.peekLast()`不可取等于號(hào)，因?yàn)檫@樣會(huì)將相等的元素全部移除，這樣會(huì)在窗口中部分元素相等時(shí)錯(cuò)誤地移除本該添加到最終結(jié)果的元素。 1. 移除失效元素和添加元素到最終結(jié)果時(shí)需要注意下標(biāo)`i`和`k`的關(guān)系，建議舉例確定。 ### 復(fù)雜度分析 時(shí)間復(fù)雜度 O(n)O(n)O(n), 空間復(fù)雜度 O(k)O(k)O(k). 空間復(fù)雜度可能不是那么直觀，可以這么理解，雙端隊(duì)列中的元素最多只能存活 k 次，因?yàn)橹挥凶畲笤氐拇婊顣r(shí)間最久，而最大元素在超過窗口長度時(shí)即被移除，故空間復(fù)雜度為 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/)