滑动窗口—最值问题
題目一：劍指 Offer 59 - II. 隊列的最大值
問題描述：
請定義一個隊列并實現(xiàn)函數(shù) max_value 得到隊列里的最大值，要求函數(shù)max_value、push_back 和 pop_front 的均攤時間復雜度都是O(1)。若隊列為空，pop_front 和 max_value?需要返回 -1。
輸入:?
- ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
- [[],[1],[2],[],[],[]]
輸出:?[null,null,null,2,1,2]
算法思路：
我們知道對于一個普通隊列，push_back 和 pop_front 的時間復雜度都是O(1)，因此我們直接使用隊列的相關(guān)操作就可以實現(xiàn)這兩個函數(shù)。對于 max_value 函數(shù)，我們通常會這樣思考，即每次入隊操作時都更新最大值：
但是當出隊時，這個方法會造成信息丟失，即當最大值出隊后，我們無法知道隊列里的下一個最大值。
為了解決上述問題，我們只需記住當前最大值出隊后，隊列里的下一個最大值即可。具體方法是使用一個雙端隊列 deque，在每次入隊時，如果 deque隊尾元素小于即將入隊的元素 value，則將小于 valuevalue 的元素全部出隊后，再將 valuevalue 入隊；否則直接入隊。這時，輔助隊列 deque 隊首元素就是隊列的最大值。
上段文字來源：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/ru-he-jie-jue-o1-fu-za-du-de-api-she-ji-ti-by-z1m/
class MaxQueue {//保存隊列所有數(shù)據(jù)Deque<Integer> dq = new LinkedList<Integer>();//保存隊列中后出隊的最大值Deque<Integer> decrease = new LinkedList<Integer>();public MaxQueue() {}public int max_value() {return this.dq.isEmpty()?-1:this.decrease.peekFirst();}public void push_back(int value) {//如果 deque隊尾元素小于即將入隊的元素 value，則將小于 valuevalue 的元素全部出隊后，再將 valuevalue 入隊while(!this.decrease.isEmpty() && this.decrease.peekLast() < value){this.decrease.removeLast();}this.decrease.offerLast(value);this.dq.offerLast(value);}public int pop_front() {int res = this.dq.isEmpty()?-1:this.dq.peekFirst();if(!this.dq.isEmpty())this.dq.removeFirst();//如果此次出隊的是剩余隊列中最大元素，則在最大值隊列中將該元素彈出if(!this.decrease.isEmpty() && res == this.decrease.peekFirst()){this.decrease.removeFirst();} return res;} }題目二：155. 最小棧
問題描述：
設(shè)計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。
- push(x) —— 將元素 x 推入棧中。
- pop()?—— 刪除棧頂?shù)脑亍?/li>
- top()?—— 獲取棧頂元素。
- getMin() —— 檢索棧中的最小元素
輸入：
- ["MinStack","push","push","push","getMin","pop","top","getMin"]
- [[],[-2],[0],[-3],[],[],[],[]]
輸出：
- [null,null,null,null,-3,null,0,-2]
算法思路：
借用一個輔助棧min_stack，用于存獲取stack中最小值。
- push()方法： 每當push()新值進來時，如果 小于等于 min_stack棧頂值，則一起push()到min_stack，即更新了棧頂最小值；
- pop()方法： 判斷將pop()出去的元素值是否是min_stack棧頂元素值（即最小值），如果是則將min_stack棧頂元素一起pop()，這樣可以保證min_stack棧頂元素始終是stack中的最小值。
- getMin()方法： 返回min_stack棧頂即可。
min_stack作用分析：
- min_stack等價于遍歷stack所有元素，把升序的數(shù)字都刪除掉，留下一個從棧底到棧頂降序的棧。
- 相當于給stack中的降序元素做了標記，每當pop()這些降序元素，min_stack會將相應的棧頂元素pop()出去，保證其棧頂元素始終是stack中的最小元素。
復雜度分析：
- 時間復雜度 O(1) ：壓棧、出棧、獲取最小值的時間復雜度都為 O(1) 。
- 空間復雜度 O(N) ：包含 N 個元素輔助棧占用線性大小的額外空間。
題目三：239. 滑動窗口最大值
問題描述：
給你一個整數(shù)數(shù)組 nums，有一個大小為?k?的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。你只可以看到在滑動窗口內(nèi)的 k?個數(shù)字。滑動窗口每次只向右移動一位。返回滑動窗口中的最大值。比如輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3，輸出：[3,3,5,5,6,7]
- 滑動窗口的位置 ? ? ? ? ? ? ? ?最大值
- --------------- ? ? ? ? ? ? ? -----
- [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
算法思路：
這個題目，算是很經(jīng)典的題目，我們的滑動窗口主要分為兩種，一種的可變長度的滑動窗口，一種是固定長度的滑動窗口，這個題目算是固定長度的代表。今天我們用雙端隊列來解決我們這個題目，學會了這個題目的解題思想你可以去解決一下兩道題目 劍指 Offer 59 - II. 隊列的最大值，155. 最小棧，雖然這兩個題目和該題類型不同，但是解題思路是一致的，都是很不錯的題目，我認為做題，那些考察的很細的，解題思路很難想，即使想到，也不容易完全寫出來的題目，才是能夠大大提高我們編碼能力的題目，希望能和大家一起進步。這個題目我們用到了雙端隊列，隊列里面保存的則為每段滑動窗口的最大值。我們先來了解下雙端隊列吧，隊列我們都知道，是先進先出，雙端隊列呢？既可以從隊頭出隊，也可以從隊尾出隊，則不用遵循先進先出的規(guī)則。下面我們通過一個動畫來了解一下吧。
?
好啦，我們了解雙端隊列是什么東東了，下面我們再通過一個動畫，來看一下代碼的執(zhí)行過程吧，相信各位一下就能夠理解啦。我們就通過題目中的例子來表述。nums = [1,3,-1,-3,5,3,6,7], k = 3
?
不知道通過上面的例子能不能給各位描述清楚，如果不能的話，我再加把勁，各位看官，請接著往下看。我們將執(zhí)行過程進行拆解：
是不是懂啦，再回去看一遍視頻吧。祝大家新年快樂，天天開心呀！
上段文字來源：https://leetcode-cn.com/problems/sliding-window-maximum/solution/zhe-hui-yi-miao-dong-bu-liao-liao-de-hua-7fy5/
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length-k+1];Deque<Integer> dq = new LinkedList<Integer>();//先將第一個窗口的元素按單調(diào)遞減規(guī)則存如雙端隊列中；for(int i=0; i<k; i++){while(!dq.isEmpty() && nums[i]>dq.peekLast())dq.removeLast();dq.offerLast(nums[i]);}res[0]=dq.peekFirst();//移動窗口for(int i=1; i< nums.length-k+1; i++){//雙端隊列的頭元素已經(jīng)不在當前窗口中if(dq.peekFirst()==nums[i-1])dq.removeFirst();//維護單調(diào)遞減隊列while(!dq.isEmpty() && nums[i+k-1]>dq.peekLast())dq.removeLast();dq.offerLast(nums[i+k-1]);res[i]=dq.peekFirst();}return res;} }?
總結(jié)
- 上一篇： 注册中心—组件—Consul
- 下一篇： Java集合—PriorityQueue