【題目敘述】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;
}