一、單調隊列
? ?用來維護一段區間內的最大值或最小值，例如滑動窗口、區間最值等問題。
基本概念
單調隊列是一種存儲數據的隊列，其中元素的順序是單調遞增或單調遞減的。在算法競賽中，我們一般使用兩個單調隊列，一個維護單調遞增序列，另一個維護單調遞減序列。單調隊列是一個雙端隊列。
代碼如下：
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;void output(vector<int>& arr) {int n = arr.size(), len = 0;for (int i = 0; i < n; i++) len += printf("%3d", i);cout << "\n";for (int i = 0; i < len; i++)printf("-");cout << "\n";for (int i = 0; i < n; i++) len += printf("%3d", arr[i]);cout << "\n";
}int main(){int n, k;cin >> n >> k;vector<int> arr;deque<int> q;for (int i = 0, a; i < n; i++) {cin >> a;arr.push_back(a);}output(arr);for (int i = 0; i < n; i++) {while (!q.empty() && arr[q.back()] > arr[i])q.pop_back();q.push_back(i); //壓入下標if (i - q.front() == k) q.pop_front(); //彈出隊頭printf("[%d, %d] = arr[%d] = %d \n",max(i - k + 1, 0), i,q.front(),arr[q.front()]);}
}
滑動窗口
154. 滑動窗口 - AcWing題庫
滑動窗口是一類問題，需要在一個長度為n的序列中，找到所有長度為k的連續子序列中的最大值或最小值。使用單調隊列可以在O(n)的時間復雜度內解決該問題。
具體做法如下：
（1）將前k個元素插入單調隊列中，并記錄隊列的最大值或最小值。
（2）從第k+1個元素開始，每次將一個新的元素插入單調隊列中。
（3）插入時，先將隊列中所有小于等于該元素的隊尾元素出隊，保證隊列中的元素單調遞減。
（4）將該元素插入隊尾，并記錄隊列的最大值或最小值。
（5）將長度為k的子序列的最大值或最小值輸出即可。
方法1：（數組實現）
#include <iostream>
using namespace std;const int N = 1e6 + 10;
int q[N], a[N]; //數組q用來存下標
int main() {int n, k;cin >> n >> k;for (int i = 0; i < n; i++) cin >> a[i];//找滑動窗口最小值int hh = 0, tt = -1;for (int i = 0; i < n; i++) {if (i - q[hh] == k) hh++; //隊頭彈出元素while (hh <= tt && a[q[tt]] > a[i]) tt--; //隊尾彈出元素q[++tt] = i; //壓入下標if (i - k + 1 >= 0)printf("%d ", a[q[hh]]);}printf("\n");//找滑動窗口最大值hh = 0, tt = -1;for (int i = 0; i < n; i++) {if (i - q[hh] == k) hh++; //隊頭彈出元素while (hh <= tt && a[q[tt]] < a[i]) tt--; //隊尾彈出元素q[++tt] = i; //壓入下標if (i - k + 1 >= 0)printf("%d ", a[q[hh]]);}return 0;
}
方法2：（雙端隊列）
#include <iostream>
#include <deque>
#include <vector>
using namespace std;int main() {int n, k;cin >> n >> k;vector<int> arr(n);deque<int> q;for (int i = 0; i < n; i++)cin >> arr[i];for (int i = 0; i < n; i++) {if (i - q.front() == k) q.pop_front();while (!q.empty() && arr[q.back()] > arr[i])q.pop_back();q.push_back(i);if (i - k + 1 >= 0) cout << arr[q.front()] << " ";}cout << endl;q.clear();for (int i = 0; i < n; i++) {if (i - q.front() == k) q.pop_front();while (!q.empty() && arr[q.back()] < arr[i])q.pop_back();q.push_back(i);if (i - k + 1 >=0) cout << arr[q.front()] << " ";}return 0;
}
區間最值
135. 最大子序和 - AcWing題庫
需要在一個長度為n的序列中，找到所有長度為k的子序列中的最大值或最小值。使用單調隊列可以在O(n)的時間復雜度內解決該問題。
其實現方法與上面類似，但是需要注意：
- 區間最值問題是在不限制子序列連續性的情況下，找到子序列中的最大值或最小值。
- 而滑動窗口問題則是在限制子序列必須連續的情況下，找到所有長度為k的子序列中的最大值或最小值。
方法1：（數組實現）
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;typedef long long LL;const int N = 1e6 + 10;
int q[N];
LL s[N];
int main()
{int n, m;cin >> n >> m;//處理為前綴和序列for (int i = 1; i <= n; i++) {cin >> s[i];s[i] += s[i - 1];}LL res = -1e10;int hh = 0, tt = 0;for (int i = 1; i <= n; i++) {if (i - q[hh] > m) hh++;res = max(res, s[i] - s[q[hh]]);while (hh <= tt && s[q[tt]] >= s[i]) tt--;q[++tt] = i;}cout << res << "\n";return 0;
}
方法2：（雙端隊列）
#include <iostream>
#include <algorithm>
#include <cstring>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;int main()
{int n, m;cin >> n >> m;//處理前綴和vector<LL> s(n + 1);s.push_back(0);deque<LL> q;for (int i = 1; i <= n; i++) {cin >> s[i];s[i] += s[i - 1];}q.push_back(0);LL res = -1e6;for (int i = 1; i <= n; i++) {if (i - q.front() > m) q.pop_front();res = max(res, s[i] - s[q.front()]);while (!q.empty() && s[q.back()] >= s[i]) q.pop_back();q.push_back(i);}cout << res << "\n";return 0;
}
二、單調棧
基本概念
單調棧實際上就是棧，只是利用了一些巧妙的邏輯，使得每次新元素入棧后，棧內的元素都保持有序（單調遞增或單調遞減），即從隊首不彈出元素的單調隊列就是單調棧。
作用：用于找最近小于關系（單調遞增）和最近大于關系（單調遞減）
代碼如下：
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;void output(vector<int>& arr) {int n = arr.size(), len = 0;for (int i = 0; i < n; i++) len += printf("%3d", i);cout << "\n";for (int i = 0; i < len; i++)printf("-");cout << "\n";for (int i = 0; i < n; i++) len += printf("%3d", arr[i]);cout << "\n";
}int main(){int n;cin >> n;vector<int> arr;arr.push_back(-1); //假如極小值為-1stack<int> s;for (int i = 0, a; i < n; i++) {cin >> a;arr.push_back(a);}arr.push_back(-1); //假如極小值為-1vector<int> l(arr.size() + 1), r(arr.size() + 1);output(arr);//右側for (int i = 0; i < arr.size(); i++) {while (!s.empty() && arr[s.top()] > arr[i]) {r[s.top()] = i;s.pop();}s.push(i);}//左側 (倒著掃描)while (!s.empty()) s.pop();for (int i = arr.size() - 1; i >= 0; i--) {while (!s.empty() && arr[s.top()] > arr[i]) {l[s.top()] = i;s.pop();}s.push(i);}for (int i = 1; i <= n; i++) {printf("arr[%d] = %d, right : arr[%d] = %d, left : arr[%d] = %d\n",i, arr[i],r[i], arr[r[i]],l[i], arr[l[i]]);}return 0;
}
數組實現單調棧：
830. 單調棧
#include <iostream>
using namespace std;
const int N = 10010;int stk[N], tt ;
int main()
{int n;cin >> n;while(n--){int x;cin>>x;while(tt&&stk[tt]>=x) tt--;if(tt==0) printf("-1 ");else printf("%d ",stk[tt]);stk[++tt]=x;}return 0;
}三、總結
單調隊列：擅長維護區間【最大/最小】值，最小值對應單調遞增隊列
單調棧：擅長維護最近【大于/小于】關系，
從左側先入棧就是維護左側最近關系
從右側先入棧，就是維護右側最近關系。
