【題解】ZeroJudge a146: Sliding Window

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a146
【解題想法】Monotonic Queue 單調隊列【筆記
注意:本題會出現 k > n 的測資,需額外處理。

【方法1】Monotonic Queue 單調隊列

#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;
}

【方法2】multiset

  • 利用multiset的自動排序特性
  • Line-23:移除過時的資料
  • Line-27:*st.begin() 為區間最小值
  • Line-28:*st.rbegin() 為區間最大值
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
int a[1000005];
multiset<int> st;
vector<int> mn, mx;

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];
		}
		mn.clear();
		mx.clear();
		st.clear();
		for (int i=0; i<n; i++){
			if (i >= k) {
				st.erase(st.lower_bound(a[i-k]));
			}
			st.insert(a[i]);
			if (i >= k-1) {
				mn.push_back(*st.begin());
				mx.push_back(*st.rbegin());
			}
		}
		if (k > n) {
			mn.push_back(*st.begin());
			mx.push_back(*st.rbegin());
		}
		cout << mn[0];
		for (int i=1; i<mn.size(); i++){
			cout << ' ' << mn[i];
		}
		cout << '\n';

		cout << mx[0];
		for (int i=1; i<mx.size(); i++){
			cout << ' ' << mx[i];
		}
		cout << '\n';
	}
	return 0;
}
分享本文 Share with friends