480. 滑动窗口中位数

难度艰难

中位数是有序序列最两头的那个数。如果序列的长度是偶数，则没有最两头的数；此时中位数是最两头的两个数的平均数。

例如：

  • [2,3,4]，中位数是 3
  • [2,3]，中位数是 (2 + 3) / 2 = 2.5

给你一个数组 nums_，有一个长度为 _k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右挪动 1 位。你的工作是找出每次窗口挪动后失去的新窗口中元素的中位数，并输入由它们组成的数组。
示例：

给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
窗口地位                      中位数---------------               -----[1  3  -1] -3  5  3  6  7       1 1 [3  -1  -3] 5  3  6  7      -1 1  3 [-1  -3  5] 3  6  7      -1 1  3  -1 [-3  5  3] 6  7       3 1  3  -1  -3 [5  3  6] 7       5 1  3  -1  -3  5 [3  6  7]      6 因而，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。
// 暴力解法class Solution1 {public:    vector<double> medianSlidingWindow(vector<int> &nums, int k) {        int size = nums.size();        vector<double> res;        for (int i = 0; i < size - k + 1; ++i) {            vector<int> temp(nums.begin() + i, nums.begin() + i + k);            sort(temp.begin(), temp.end());            if (k & 1) {                res.emplace_back(temp[k / 2]);            } else {                res.emplace_back((temp[k / 2] + temp[k / 2 - 1]) / 2.0);            }        }        return res;    }};
// 官网解法，规范性好class DualHeap {private:    priority_queue<int, vector<int>, less<int>> small;    // 大根堆存比拟小的数 priority_queue<int, vector<int>, greater<int>> large; // 小根堆存比拟大的数 unordered_map<int, int> delay;    int smallSize;    int largeSize;    int k;public:    DualHeap(int _k) : k(_k), smallSize(0), largeSize(0) {}    template<class T>    void pop(T &heap) {        while (!heap.empty()) {            int temp = heap.top();            if (delay.count(temp)) {                --delay[temp];                if (delay[temp] == 0)                    delay.erase(temp);                heap.pop();            } else break;        }    }    void balance() {        if (smallSize-2 == largeSize) {            large.emplace(small.top());            small.pop();            --smallSize;            ++largeSize;            pop(small);        }        if (smallSize < largeSize) {            small.emplace(large.top());            large.pop();            --largeSize;            ++smallSize;            pop(large);        }    }    void insert(int x) {        if (small.empty() || x <= small.top()) {            small.emplace(x);            ++smallSize;        } else {            large.emplace(x);            ++largeSize;        }        balance();    }    void erase(int x) {        ++delay[x];        if (x <= small.top()) {            --smallSize;            if (x == small.top())                pop(small);        } else {            --largeSize;            if (x == large.top()) {                pop(large);            }        }        balance();    }    double getMedian() {        return k & 1 ? small.top() : small.top() / 2.0 + large.top() / 2.0;    }};class Solution2 {public:    vector<double> medianSlidingWindow(vector<int> &nums, int k) {        int size = nums.size();        DualHeap dh(k);        vector<double> res;        for (int j = 0; j < k; ++j) {            dh.insert(nums[j]);        }        for (int i = k, j = 0; i <= size; ++i, ++j) {            res.emplace_back(dh.getMedian());            dh.insert(nums[i]);            dh.erase(nums[j]);        }        res.emplace_back(dh.getMedian()); // 要害        return res;    }};作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/sliding-window-median/solution/hua-dong-chuang-kou-zhong-wei-shu-by-lee-7ai6/起源：力扣（LeetCode）