- 【用途】Monotonic Stack 單調棧的升級版，使用deque實作，單調隊列支援pop_front( )，可以根據資料enqueue的時間順序刪除元素。單調隊列可以用來找尋區間的最大或最小值。
- 【時間複雜度】O(N)
- 【範例】ZeroJudge a146: Sliding Window
- 注意：本題會出現 k > n 的測資，需額外處理(Line-27)。
- 運用兩次單調隊列，一次找區間最小值(下圖例)，一次找區間最大值。
- deque存放資料的index，用來維護區間資料的單調遞增性質，因此a[dq.front()]即為區間最值。
- Line-17：pop過時(超出區間)的資料。
- Line-20：pop違反單調遞增性的資料。
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
int a[1000005];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
while (cin >> n >> k) {
for (int i=0; i<n; i++){
cin >> a[i];
}
deque<int> dq;
for (int i=0; i<n; i++){
while (dq.size() && dq.front() <= i - k){
dq.pop_front();
}
while (dq.size() && a[dq.back()] > a[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i == k - 1) cout << a[dq.front()];
if (i > k - 1) cout << ' ' << a[dq.front()];
}
if (k > n) {
cout << a[dq.front()];
}
cout << '\n';
while (dq.size()) dq.pop_back();
for (int i=0; i<n; i++){
while (dq.size() && dq.front() <= i - k){
dq.pop_front();
}
while (dq.size() && a[dq.back()] < a[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i == k - 1) cout << a[dq.front()];
if (i > k - 1) cout << ' ' << a[dq.front()];
}
if (k > n) {
cout << a[dq.front()];
}
cout << '\n';
}
return 0;
}
【更多練習】Codeforces 1237D Balanced Playlist【題解】
【更多練習】Codeforces 1195E. OpenStreetMap【題解】