a146 - Sliding Window
題目描述
題目給定一個長度為 n 的陣列和一個大小為 k 的滑動窗口。要求在滑動窗口從陣列左端滑動到右端的過程中，輸出每個窗口中元素的最小值和最大值。
解題思路
本題可以使用多重集合 (multiset) 來有效地追蹤滑動窗口中的最小值和最大值。多重集合允許儲存重複的元素，並且可以快速地找到最小值和最大值。
算法步驟如下：
- 初始化一個大小為 k 的滑動窗口，並將窗口中的元素插入到多重集合中。
- 對於每個滑動窗口的位置：
- 輸出多重集合中的最小值和最大值。
- 將滑動窗口最左邊的元素從多重集合中移除。
- 將滑動窗口最右邊的新元素插入到多重集合中。
- 在所有窗口都滑動完畢後，輸出最後一個窗口的最小值和最大值。
使用多重集合的優勢在於，它能夠在 O(log k) 的時間內插入、刪除和查找最小值/最大值，使得整個算法的時間複雜度降低。
複雜度分析
- 時間複雜度: O(n log k)
- 空間複雜度: O(k)
程式碼
#include <iostream>
#include <set>
using namespace std;
int n,k,p,a[1000005],b[1000005],c[1000005];
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> k){
k=min(n,k);
multiset <int> s;
for(int i=0;i<k;++i){
cin >> a[i];
s.insert(a[i]);
}
for(int i=k;i<n;++i){
cin >> a[i];
b[i-k]=*s.begin();
c[i-k]=*--s.end();
s.erase(a[i-k]);
s.insert(a[i]);
}
b[n-k]=*s.begin();
c[n-k]=*--s.end();
for(int i=0;i<=n-k;++i){
if(i)cout << " ";
cout << b[i] ;
}
cout << "\n";
for(int i=0;i<=n-k;++i){
if(i)cout << " ";
cout << c[i];
}
cout << "\n";
}
}