【題解】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;
    }
};