單調棧單調隊列【算法進階】

這周學完之后最大的收獲就是單調棧和單調隊列了！！！感覺好厲害能把時間復雜度瞬間壓縮為O(N)，不行我必須再紀念一下這么美妙的算法！！！

單調棧問題：

如果題目要求一個元素左邊或右邊的第一個大于或小于他的元素（一把不會直接告訴你，需要你在分析問題時對是否有單調性或者是否需要單調性進行分析），或者讓你求一段連續子數組的左右邊界問題（如柱狀圖的最大矩形面積）時（力扣上問題84、85、或者洛谷上最大區間問題等等），可以優先考慮用單調棧，而如果要以當前元素為右端點，在他之前找到極值時，一般用滑動窗口，而且滑動窗口一般不會只考雙端隊列，而是用單調隊列進行優化（隊首/或者說越靠前一定是最優選擇）例如力扣862.和至少為K的子數組，先用前綴和預處理，要想用最短的長度滿足大于等于K 那么就要讓窗口盡量小，且遍歷時右端元素與隊首元素的差最大，也就是讓隊首元素最小，固需要維護單調遞增隊列，用于找到目前以這個元素為右端點時前面的最小值！

進階題目練習：

1、柱狀圖中的最大矩形

這個題目就是讓求一段連續的區間，然后讓區間長度與區間內的所有元素的最小值的乘積最大，首先用暴力的方法來想，那就是遍歷每一個矩形，那么怎么優化呢，我們可以遍歷每一個元素，然后以當前元素為最小值的連續矩形，這樣我們就從遍歷每一個矩形變成了遍歷每一個可能作為答案的矩形（最多有n個矩形），那么怎么去實現找到以當前元素為最小值的矩形呢？開個循環往兩邊找邊界？誒？往兩邊找？邊界？那不就是分別找當前元素兩邊的第一個小于他的位置嗎？恭喜你，想到了正解 -> 單調遞增棧優化，通過正反兩次單調遞增棧找到以這個元素為最小值的矩形的左右邊界即可。????????【從暴力優化到正解！??】

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int ans = 0,n = heights.size();vector<int> l(n),r(n);stack<int> st;for(int i=n-1;i>=0;i--){int t = heights[i];while(!st.empty() && heights[st.top()] >= t) st.pop();r[i] = (st.empty() ? n : st.top());st.push(i);}st = stack<int> ();for(int i=0;i<n;i++){int t = heights[i];while(!st.empty() && heights[st.top()] >= t) st.pop();l[i] = (st.empty() ? -1 : st.top());st.push(i);}for(int i=0;i<n;i++){ans = max(ans,(r[i] - l[i] - 1)*heights[i]);}return ans;}
};

至于最大區間，和上面的題一模一樣，就當復習了，代碼略~

什么？難度又要升級了？來看一下：最大矩形

還是一樣，先想暴力，枚舉每一個矩形，找出最大值，從上往下來看，這不是和前面的題目一樣嗎，從一個個柱狀圖中找出最大的連續矩形（可是有可能同一列的柱狀圖不連續啊）那就只能一行一行的找嘍，那就對每一行進行上一題的步驟，不斷更新最大值，總比純暴力枚舉每一個矩形強吧，時間復雜度是O(N*M)，看一眼數據范圍能過。

怎么實現呢？首先進行預處理，可以先把每一行的連續柱狀圖表示出來，然后對每一行進行兩次單調棧查詢以當前元素為最小值的矩陣的左右范圍，不斷更新即可！

class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {int n = matrix.size();//n行int m = matrix[0].size();//m列vector<vector<int>> dp(n,vector<int>(m,0));//預處理值（這行中這一列的連續的1的個數即：高度）for(int j=0;j<m;j++)for(int i=0;i<n;i++)if(matrix[i][j] == '1')dp[i][j] = (i == 0) ? 1 : dp[i-1][j] + 1;int ans=0;for(int i=0;i<n;i++)//對每一行都仿照84題的解法{vector<int> l(m,0),r(m,0);//以當前元素為最小值的左右區間stack<int> st;for(int j=0;j<m;j++){int t = dp[i][j];while(!st.empty() && dp[i][st.top()] >= t) st.pop();l[j] = st.empty() ? -1 : st.top();st.push(j);}st = stack<int> ();for(int j = m-1;j>=0;j--){int t = dp[i][j];while(!st.empty() && dp[i][st.top()] >= t) st.pop();r[j] = st.empty() ? m : st.top();st.push(j);}for(int j=0;j<m;j++){int x = r[j] - l[j] - 1;int S = x*dp[i][j];ans = max(ans,S);}}return ans;}
};

太美妙了這單調棧！

滑動窗口&單調隊列優化

雙端隊列滑動窗口（常規滑動窗口）

單調隊列滑動窗口
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1.維護左端點

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2.維護右端點的隊列單調性

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3.元素入隊?

長度最小的子數組

由于每一個元素都大于0，所以前綴和本身就具有單調性，無需用到單調隊列進行優化，直接二分前綴和即可，或者用雙端隊列/雙指針模擬滑動窗口來實現。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans=1e8;deque<int> q;int sum=0;for(int i=0;i<nums.size();i++){q.push_back(i);//本身就具有單調性 所以可以直接進隊sum+=nums[i];while(!q.empty() && sum>=target){ans = min(ans,q.back() - q.front() + 1);sum-=nums[q.front()];q.pop_front();}  }return ans==1e8 ? 0 : ans;}
};

當然更推薦符合大眾的模板風格：維護左端，維護結束后再判斷答案

這樣寫的好處是只要遍歷到了一個合法答案那么之后的所有遍歷中答案都合法了，所以再更新答案時要加上if判斷合法答案，防止一次while都沒進過就應該是沒有合法答案了所以while中是多余元素的判斷！

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans=1e8;deque<int> q;int sum=0;for(int i=0;i<nums.size();i++){q.push_back(i);//本身就具有單調性 所以可以直接進隊sum+=nums[i];while(!q.empty() && sum - nums[q.front()]>=target){sum-=nums[q.front()];q.pop_front();} //if是必須要加的防止一次while都沒進入過！！！if(sum >= target) ans = min(ans,q.back() - q.front() + 1);}return ans==1e8 ? 0 : ans;}
};

和至少為K的最短子數組

這道題讓求滿足一定條件的子數組，而且還要求出最短的長度，首先想暴力怎么實現，遍歷每一個子數組，再計算區間和（前綴和優化），然后再找出最小的滿足條件的子數組，顯然時間復雜度是通過不了此題的，那么就開始想怎么去優化一下，首先毋庸置疑要先用前綴和進行預處理，然后再找滿足條件的子區間 -> 要想使區間和大于等于K，那么就要在遍歷數組時，讓區間的左端點盡量的小，因為這樣才能保證區間盡可能的大（首先要保證存在性，然后再取最優解），而且還要保證區間的左端點一定要比右端點小，也就是說在遍歷時，如果當前元素是目前為止出現的最小值了，那么就應該將這個元素為起點繼續往后找了（因為越小的值越作為起點，繼續往后遍歷時肯定是要找他之前的最小值），這樣也就符合單調隊列的性質了，所以單調隊列優化滑動窗口可以適用于求一個元素前面的最值問題，基本步驟是先維護左端點（并計算答案【有存在解時】）再通過右端點維護隊列的單調性，然后最后再從隊尾push_back新元素。所以就有一下代碼：

class Solution {
public:int shortestSubarray(vector<int>& nums, int k) {int n = nums.size();vector<long long> sum(n+1,0);//前綴和預處理for(int i=0;i<nums.size();i++) sum[i+1] = sum[i] + nums[i];int ans = 1e8;deque<int> q;q.push_back(0);//因為是前綴和 所以要多往前壓一個下標for(int i=1;i<=n;i++){int t = sum[i];//在滿足條件情況下更新ans并將隊首彈出while(!q.empty() && sum[i] - sum[q.front()] >= k){//因為往前移了一個元素 所以無需-1ans = min(ans,i-q.front());q.pop_front();}//維護單調遞增隊列while(!q.empty() && sum[q.back()] >= t) q.pop_back();q.push_back(i);}return ans==1e8 ? -1 : ans;}
};

最小覆蓋子串?

附：先加入新元素和后加入新元素的判斷：

先加入新元素和后加入區別：

先加入是因為while中是合法解，要在while中找答案，while之后可能不合法

后加入是因為while中是不合法解，while之前可能還是不合法，while之后才是合法解

????????????????????????????????????????????????????????????????????????????????????????????????????????【在合法解中找答案！】?

總之主要就是看什么時候加入元素能可能出現合法解?。

1-先加入新元素合法就先加入新元素

2-先加入新元素有可能不合法就先解決矛盾后加入

代碼如下：

class Solution {
public:string minWindow(string s, string t) {int min_len = s.size() + 1;//滿足條件的解的長度int l = -1;//滿足條件的解的起始位置unordered_map<char,int> v;//記錄t中需要的字符 不能用bool因為可重復unordered_map<char,int> mp;//用于記錄當前的窗口中的所有字符出現的情況for(int i=0;i<t.size();i++) v[t[i]] ++;//預處理vdeque<int> q;//滑動窗口int num=0;//當前窗口中的t中所需字符的數量for(int i=0;i<s.size();i++){q.push_back(i);//先加入 因為加入新元素后有可能滿足條件if(v[s[i]] && mp[s[i]] < v[s[i]]) num++;//累加nummp[s[i]]++;//考慮到所有元素 因為要求最小值 不是t中的元素就可以出去 從而找到最小值while(!q.empty() && mp[s[q.front()]] > v[s[q.front()]]){//沒有用的（多余的t中的元素的或t中沒有出現的）元素就扔掉mp[s[q.front()]]--;q.pop_front();}if(num == t.size() && q.back() - q.front() + 1 < min_len){//只要有滿足條件的解了就更新min_len = q.back() - q.front() + 1;l = q.front();}}return l > -1 ? s.substr(l,min_len) : "";}
};

后加入的例題：最長優雅子數組詳解請看前幾天的這個博客?。

代碼如下：

class Solution {
public:int longestNiceSubarray(vector<int>& nums) {int ans=0,num=0;//num是當前窗口中的或運算deque<int> q;for(int i=0;i<nums.size();i++){while(!q.empty() && num & nums[i])//有交集 用按位或運算優化代碼{num ^= nums[q.front()];//維護左端點 q.pop_front();}num |= nums[i];//或運算的優點：二進制位上只要有一個為1就為1（說明有人占位了 不能再占了 后續判斷待判元素時就不需要一個一個按位與了 只需要對num來按位與即可 因為此時的num就已經是窗口中的所有元素按位或的結果了）q.push_back(i);//維護右端點 將待判元素入隊//解決完矛盾之后就一定是合法解了 直接更新即可ans = max(ans,q.back() - q.front() + 1);}return ans;}
};

總結：

單調棧總結：

單調棧可以求出一個元素的一邊的第一個大于或小于他位置，所以可以適用于求連續子數組的邊界問題如力扣-接雨水、力扣-柱狀圖中的最大矩形、力扣-最大矩形等，再有就是一些比較明顯的求一邊的第一個大于或小于他的元素的位置了，就不過多贅述了。

滑動窗口總結：

滑動窗口分為兩種：

1.雙端隊列實現：如果新元素與之前的元素沒有沖突或影響，一般可以先入隊，再維護左端點，但是如果新元素與之前的元素有了沖突（最長優雅子數組），就需要先維護左端點，直到沒有沖突時再加入新元素，這樣就能保證每次遍歷中的隊列都是一個滿足題目要求的隊列了，所以每次都更新最優解即可。

總之都是要先保證有解，再取最優解。?

2.單調隊列優化：

一般的步驟就是先維護左端點，再通過維護右端點來維護隊列的單調性，然后再加入新元素（一般用于找一個元素之前的最值）。

雙端隊列實現：隊列這個窗口就是維護的滿足條件的子數組區間，一般見于最短最長連續子數組

單調隊列實現：隊列中的是這個元素之前的單調小于或大于這個元素的值，而且隊首就是最值。

/*
----------------=-=============================+++++++++++++++++++++++++++++**+*********************
-------------------==-=-=======================++=+++++++++++++++++++++++++++++*********************
:----------------------==========================+++++++++++++++++++++++++++++**+*******************
::-----------------------===-=-==========================+++++++++++++++++++++++++*+****************
:::::------------------------=====---::::...............:::::-==++++++++++++++++++++++*++***+*******
::::::-:-------------------==--::...............................::-=++++++++++++++++++*++++*++++++++
::::::::-:----------------:..........................................:-=++++++++++++++++++*+++++++++
::::::::::::-----------:.   ............................................:=+++++++++++++++++*+*******
:::::::::::::::------.    .............................::.................:-+++++++++++++++++++*****
::::::::::::::::-=:.   ...............................::...::::--:...........-+++++++++++++++++****+
:::::::::::::::--: .................................:-:..::..  .+*-:...........-++++++++++++++++++++
:::::::::::::-=:........:...........................-:..-.      +@#--:..........:+++++++++++++++++++
::::::::::::-=:.........::.............................==     .+%%%#.-:.........:-++++++++++++++++++
...::::::::--.....:--:::.::...........................:%%=::-*%%%%%%+ -:.......:---=++++++++++++++++
..::::::::--.....:+*. .::.::..........................+%%%%%%%%%%%%%%. -......:-----=+++++++++++++++
.......:.:=....:-=%=    ::............................*%%%%%%%%%%%%%%= :-.....:------=*+++++++++++++
.........=:....-:#%#.   =+...........:...............:#%%%%%%%%%%%#%%* .-.....:-------=*++++++++++++
........:=....:.=%%%#+=+%#:...........................#%#%==%%%%%%#%%*  -:....:--------+++++++++++++
........:-...:- +%%%%%%%%%:...........................+%*: -##%%*-*#%+  -:....:---------++++++++++++
........--...:: #%%%%%%%%%:...........................-#= .*:.###::#%-  -:....:---------++++++++++++
........-:...-. *%%#%%%%%%:............................+*=*#**####*#*...-:.....:--------=+=+++++++++
........-:...-. +%*.+@%#*#:.............................:------=====-::::......:---------*=+++++++++
........-:...-. :#-.+-##*#:.....................................................---------+===+++++++
........=:...::  +++*+#**=........::............................................---------+====++++++
........=:...:-..:*+=-::..........::..............::::::::::::::::::--==:.......:--------+====++++++
........-.....::::........::............:::--===+++++++++++++++*++++++**-.......---------+=====+++++
.......:-.........................::-==++++***+***+++++++++++++++++++++*+......:--------=*=======+++
.......-:............:::::::---==+++**+***++++++*++++++++++++++++++++++++:.....:--------=+=======+++
......:-.....::::-=+**########**+++++++*+++++++======--------------=+++++:.....:--------+=========++
......-:.....::-*##%%%#####%#*++++++++===----------------------------++++......--------++==========+
......:-........-#%########+====-------------------------------------=+*=.....:-------=+===========+
.......-:........:*%######*------------------------------------------+*+:....:-------==.:-+=========
.......:-.........:*%#####-------------------------------------------+*:.....:------=-:::.:++=======
........:-:........:+%##%*------------------------------------------++-.....:------=-..:::.-**++====
.........:-:.........=##%+-----------------------------------------++:....:------==---------++++*+++
...........--:........:*%#----------------------------------------+=:....:------==:::::::::...::::::
............:-::........-*+-------------------------------------==:....:------=-:...................
..............:--:.......:-=----------------------------------=--...::-----==-:.....................
................:--::.......:---------------------------------:...::-------=:..:....................
...................:--:.......::--------------------------::...::----=--:.-:........................
.....................:-=-:::.....:::----------------:::.....::--=---::...:-.........................
.................::::---..::::::::.......:::::.:......:::------::........-:.........................
.............:::::::-:.    ....::::::::::::::::::::------:::.............-:.........................
.........::::::...:-:      .............:::::::::........................=:.........................
......:::::......-:.  .    ..   .........................................=--::......................
...:--::........-:   ...       .   ......................................-=---::....................
:-:::.........:-:        ..   ..         ...........::::::::::::::::::::::+------:::................
::...........:-. .   . .        ........::.::::..::.:.................... :=---------::.............
............:-.        .......::........-......                       .    :=------------::::.......
...........:-. ......::::......        ::      ..           ..         . .  :=-----------------:::::
...........=:.:........      ..       .-.   ..          ..      .  .    .    .=---------------------
..........--...                ..     .- .        .                 .   .   . .:=-------------------
.........-=        .         . . .    :: ..     .    .   ..          .    ...   .-=-----------------
........:=.     .         .           -.                          .        ....  .::-=--------------
........-: .   ..  .   .         ..   -.                   ..    ... .      ..   ....::---=---------
*/