【筆記】Monotonic Queue 單調隊列

  • 【用途】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題解

分享本文 Share with friends