# 【題解】LeetCode 480. Sliding Window Median

```class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& v, int k) {
priority_queue <pair<int, int> > l;
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > r;
vector <double> ans;
if (k % 2 == 0){
int h = k/2-1;
pair <int, int> m1, m2;
for (int i = 0; i < k; i++){
l.push({v[i], i});
}
for (int i = 0; i < h; i++){
r.push(l.top());
l.pop();
}
m2 = l.top();
l.pop();
m1 = l.top();
l.pop();
ans.push_back(((double)m1.first+m2.first)/2);
for (int i = k; i < v.size(); i++){
if (v[i] < m1.first){
l.push({v[i], i});
if (v[i-k] > m2.first || (v[i-k] == m2.first && i-k >= m2.second)){
while (l.top().second <= i-k) l.pop();
r.push(m2);
m2 = m1;
m1 = l.top();
l.pop();
}
else if (m1.second == i-k){
while (l.top().second <= i-k) l.pop();
m1 = l.top();
l.pop();
}
}
else if (v[i] >= m2.first){
r.push({v[i], i});
if (v[i-k] < m1.first || (v[i-k] == m1.first && i-k <= m1.second)){
while (r.top().second <= i-k) r.pop();
l.push(m1);
m1 = m2;
m2 = r.top();
r.pop();
}
else if (m2.second == i-k){
while (r.top().second <= i-k) r.pop();
m2 = r.top();
r.pop();
}
}
else{
if (v[i-k] <= m1.first){
l.push(m1);
m1 = {v[i], i};
}
else if (v[i-k] >= m2.first){
r.push(m2);
m2 = {v[i], i};
}
}
//cout << m1.first << " " << m2.first << "\n";
ans.push_back(((double)m1.first+m2.first)/2);
}
}
else{
int h = k/2;
pair <int, int> m;
for (int i = 0; i < k; i++){
l.push({v[i], i});
}
for (int i = 0; i < h; i++){
r.push(l.top());
l.pop();
}
m = l.top();
l.pop();
ans.push_back(m.first);
for (int i = k; i < v.size(); i++){
if (v[i] < m.first){
l.push({v[i], i});
if (v[i-k] > m.first || (v[i-k] == m.first && i-k >= m.second)){
while (l.top().second <= i-k) l.pop();
r.push(m);
m = l.top();
l.pop();
}
}
else if (v[i] >= m.first){
r.push({v[i], i});
if (v[i-k] < m.first || (v[i-k] == m.first && i-k <= m.second)){
while (r.top().second <= i-k) r.pop();
l.push(m);
m = r.top();
r.pop();
}
}
ans.push_back(m.first);
}
}
return ans;
}
};
```