239. 滑動窗口最大值

輸入：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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

輸入：nums = [1], k = 1
輸出：[1]

思路：單調(diào)隊列

? ??其實這道題的解法有不同種形式，但是繞不開的就是使用單調(diào)隊列的思想，為什么呢???

? 因為如果這個時候我們不用單調(diào)隊列的話，就是說我們每次去控制這個窗口里面的最大值，如果這個窗口很大，那么時間復(fù)雜度是非常高的，因為遍歷一遍這個窗口獲取最大值的時間復(fù)雜度是 O(k)，而我們還得去遍歷這個數(shù)組的元素，那么總和起來就是 O(n*k)，這樣子在這道題是會超時的！所以我們得使用單調(diào)隊列的思想！

? 那么我們得先了解一下，什么是單調(diào)隊列！

什么是單調(diào)隊列

? 單獨隊列本質(zhì)還是一個隊列，只是我們規(guī)定這個隊列是一個單調(diào)遞減或者單調(diào)遞增隊列！??單調(diào)遞減和遞增是什么意思呢???

? 這里以單調(diào)遞減為例，因為和我們這道題比較符合！我們舉一個數(shù)學(xué)上面的例子 y = ax + b，我們知道遞減就是函數(shù)在某個區(qū)間上面的 y 隨著 x 的增大，而不斷的減小或者相等，但是如果我們定義它為單調(diào)遞減，那么這個函數(shù)則變成在 整個區(qū)間上面都是 y 隨著 x 的增大而不斷的減小！

? 一般來說，單調(diào)隊列使用 C++ 中的 deque 來實現(xiàn)會更好，因為其支持雙端的插入刪除以及獲取雙端元素！

? ??那么這道題要使用單調(diào)遞減還是單調(diào)遞增呢???

? 其實用單調(diào)遞減會更加的符合滑動窗口的原理，我們保持從隊頭的元素開始，每個元素都大于其后面的元素，這樣子像下圖一樣：

? 也就是我們**保持讓隊頭的元素是整個隊列里面最大的**！

? ??這樣子有什么好處呢???

? 我們每次取當(dāng)前窗口的最大值，那么就和這個隊頭元素有關(guān)系啦，但是我們得來維護(hù)一下這個隊列，而不同方式維護(hù)就有了不同的實現(xiàn)方法，下面我們舉兩種方法，其中我覺得最好理解的就是第一種！

1、隊列維護(hù)數(shù)組下標(biāo)

滑動窗口最大值 | 圖解單調(diào)隊列 | 最清晰易懂的講解【c++/java】

? ??為什么要維護(hù)數(shù)組的下標(biāo)呢???

? 因為每次我們需要去控制這個窗口移動，并保持讓隊列中的元素都落于這個窗口內(nèi)，所以我們得一直關(guān)注著隊列中的元素的值是在 nums 數(shù)組中的哪個位置，會不會出界，這些問題都要考慮，所以我們干脆直接用隊列來保存其數(shù)組的下標(biāo)，然后比較大小也是非常方便，因為是數(shù)組，所以有了下標(biāo)，我們直接通過 nums[i] 就能快速索引到對應(yīng)的元素，根本不用擔(dān)心效率問題！并且這樣子也非常的好控制！

? 下面我們來看看具體的步驟（下面步驟中默認(rèn)我們的隊列變量名叫做dq）：

1. 遍歷 nums 數(shù)組的每個元素
2. 每次遍歷元素的時候，先循環(huán)判斷一下隊頭元素在nums中位置是否已經(jīng)掉出了窗口范圍
   • 如果 i - k + 1 > dq.front()，說明隊頭元素已經(jīng)不落在該窗口內(nèi)了，我們就將隊頭pop掉！否則不用。
     • （值得解釋一下的是這里的 i - k + 1 其實代表的就是窗口的第一個元素下標(biāo)，也就是窗口的頭位置！其中 dq.front() 代表的是隊頭元素在 nums 中的下標(biāo)，如果我們的窗口頭位置都超過了這個隊頭元素的下標(biāo)了，那么說明這個隊頭元素不是當(dāng)前窗口內(nèi)的！）
     • （還有值得注意的是這里可以進(jìn)行循環(huán)判斷，也可以不進(jìn)行循環(huán)判斷，因為我們每次都只會對 i 進(jìn)行一次的 ++，但是為了代碼上面看起來嚴(yán)謹(jǐn)，可以將其改為循環(huán)判斷！）
3. 控制新元素 nums[i] 加入的時候保持單調(diào)遞減隊列的規(guī)則
   • 如果 nums[i] > dq.back()，此時如果直接將 nums[i] 加入隊列的話，會破壞單調(diào)遞減的規(guī)則，所以我們要將 dq.back() 進(jìn)行刪除，并且不斷循環(huán)判斷，直到隊列為空，或者遇到比 nums[i] 小或者等于的值為止！
4. 將 nums[i] 加入單調(diào)隊列
5. 最后判斷一下是否已經(jīng)到了滿足窗口大小 k 的位置了
   • 是的話則開始向數(shù)組 v 中 push 進(jìn)每次窗口最大的元素，也就是隊頭元素在 nums 中對應(yīng)位置的元素！

? 💥**注意：隊列中隊頭元素不一定是最大的，因為存放的不是數(shù)組中元素的值，而是其最大元素的下標(biāo)！**

? 其實這道題是相對比較復(fù)雜的，最好是自己先模擬這個過程！

? 下面給出代碼：

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> v;deque<int> dq;for(int i = 0; i < nums.size(); ++i){// 1、控制窗口的元素大小不大于k個，若大于則pop掉隊頭while(dq.size() > 0 && i - k + 1 > dq.front())dq.pop_front();// 2、控制新元素加入的時候保持單調(diào)遞減隊列的規(guī)則// 若新元素大于其隊尾的元素，那么則pop掉該元素，直到遇到比新元素大或者相等為止while(dq.size() > 0 && nums[i] > nums[dq.back()])dq.pop_back();// 3、將新元素加入隊列dq.push_back(i);// 4、若其循環(huán)到滿足窗口大小k的位置了，則開始向v中push進(jìn)每次最大的元素，也就是隊頭元素// 其中因為i是下標(biāo)而k是大小，所以i要加一if(i + 1 >= k)v.push_back(nums[dq.front()]);}return v;}
};

2、隊列維護(hù)數(shù)組元素值

[C++]滑動窗口最大值–單調(diào)隊列

? 這種方法可能是我們會比較先于維護(hù)數(shù)組下標(biāo)而想到的，因為通常來說我們都會先去想怎么存放這個值，而不是存放對應(yīng)下標(biāo)，也確實，這道題如果是維護(hù)元素的值，那么相對于第一種方法來說會更容易出錯一點，因為我們得去控制這個窗口移動的時候于隊列元素的關(guān)系，保持其一直是窗口內(nèi)有效元素！

? 既然隊列要維護(hù)數(shù)組元素值，那么當(dāng)然隊頭元素就和第一種方法不一樣了，這次隊頭元素肯定是隊列里面最大的，因為這是一個單調(diào)隊列，并且其存放的本身就是元素的值而不是下標(biāo)！

? 💥下面是步驟：

1. 首先可以維護(hù)隊列保持單調(diào)遞減，將 nums[i] 和隊尾元素進(jìn)行比較，若 dq.back() < nums[i] 說明需要 pop 掉隊尾元素，和方法一類似！
2. 將新元素加入隊列
3. 若其循環(huán)到滿足窗口大小 k 的位置了，則開始向 v 中 push 進(jìn)每次最大的元素，也就是隊頭元素，和方法一類似！
4. 注意還要維護(hù)隊列元素是否在窗口內(nèi)有效（因為要進(jìn)行 nums 索引，所以最好放到第三步這個判斷語句中比較安全）

? 其實和第一種方法大同小異，不同的就是它們的大小判斷等等，最重要的是這個第四步，也就是控制這個隊列中隊頭等元素是否還在合法的窗口區(qū)間內(nèi)，如果不是的話則要進(jìn)行刪除，而我們并不容易判斷這個區(qū)間，因為我們怎么知道隊頭元素對應(yīng) nums 中的下標(biāo)呢???

? 其實這就是一個難點，所以我們要改變思路：

? 💥因為每次我們只讓 i 累加一次，也就是每次遍歷只會讓 i 向后走一步，那么我們只需要跟著遍歷每次的窗口第一個元素，是否和當(dāng)前隊頭的元素一樣，一樣的話說明遍歷下一個元素的時候，這個元素就已經(jīng)不再是窗口內(nèi)的元素了，所以我們就把這個隊頭元素給 pop 掉！而這個窗口的頭位置就是 i-k+1 處，但是由于窗口一開始還沒達(dá)到 k 個，所以要建立在條件是 i+1 >= k 的基礎(chǔ)之上！

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> v;deque<int> dq;for(int i = 0; i < nums.size(); ++i){// 1、首先可以維護(hù)隊列保持單調(diào)遞減，將nums[i]和隊尾元素進(jìn)行比較while(dq.size() > 0 && dq.back() < nums[i])dq.pop_back();// 2、將新元素加入隊列dq.push_back(nums[i]);// 3、若其循環(huán)到滿足窗口大小k的位置了，則開始向v中push進(jìn)每次最大的元素，也就是隊頭元素// 其中因為i是下標(biāo)而k是大小，所以i要加一if(i + 1 >= k){v.push_back(dq.front());// 4、注意還要維護(hù)隊列元素（因為要進(jìn)行nums索引，所以最好放到if(i+1>=k)這個判斷語句中比較安全）if(dq.size() > 0 && dq.front() == nums[i - k + 1])dq.pop_front();}}return v;}
};