480. Sliding Window Median

https://leetcode.com/problems/sliding-window-median/

实时返回大小为K的滑动窗口中位数。维持窗口内排好序，每次插入新元素移除老元素再找出中位数。可以用插入排序，窗口每次移动需要O(K)时间插入和删除。也可以用BST，维持记录左中位数的指针，根据新进入元素在指针左还是右，以及被移除元素在左还是右总共四种情况对该如何变动指针分类讨论，参考:

/*
 * @lc app=leetcode id=480 lang=cpp
 *
 * [480] Sliding Window Median
 *
 * https://leetcode.com/problems/sliding-window-median/description/
 *
 * algorithms
 * Hard (33.54%)
 * Likes:    510
 * Dislikes: 53
 * Total Accepted:    31.8K
 * Total Submissions: 93.8K
 * Testcase Example:  '[1,3,-1,-3,5,3,6,7]\n3'
 *
 * Median is the middle value in an ordered integer list. If the size of the
 * list is even, there is no middle value. So the median is the mean of the two
 * middle value.
 * Examples: 
 * [2,3,4] , the median is 3
 * [2,3], the median is (2 + 3) / 2 = 2.5 
 * 
 * Given an array nums, there is a sliding window of size k which is moving
 * from the very left of the array to the very right. You can only see the k
 * numbers in the window. Each time the sliding window moves right by one
 * position. Your job is to output the median array for each window in the
 * original array.
 * 
 * For example,
 * Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
 * 
 * 
 * Window position                Median
 * ---------------               -----
 * [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
 * 
 * 
 * Therefore, return the median sliding window as [1,-1,-1,3,5,6].
 * 
 * Note: 
 * You may assume k is always valid, ie: k is always smaller than input array's
 * size for non-empty array.
 */
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        const int N = nums.size();
        vector<double> res;
        if (k == 0) return res;
        multiset<int> w(nums.begin(), nums.begin() + k);
        // 指向左中位数
        auto mid = next(w.begin(), (k - 1) / 2);
        for (int i = k; i <= N; ++i) {
            res.push_back(((double)(*mid) + *next(mid, (k + 1) % 2)) / 2.0);
            if (i == N) break;
            w.insert(nums[i]);
            // 插入新元素
            if (nums[i] < *mid) --mid; 
            // 删除老元素
            if (nums[i - k] <= *mid) ++mid;
            w.erase(w.lower_bound(nums[i - k]));
        }
        return res;
    }
};