[LeetCode]Sliding Window Median

这道题整体来讲和Find Median From Data Stream是很相似的，做法也很类似，我们可以用multiset加mid指针，mid指针仍然需要满足下列条件：

• 如果长度为奇数，指向中间
• 如果长度为偶数，指向中间较大的那个

每次插入的时候：

• 如果当前长度为奇数
• 如果插入的数小于mid对应的值，--mid，这样mid指向中间较小的一个
• 如果插入的数大于mid的值，不动，这样mid指向中间较小的一个
• 如果当前长度为偶数
• 如果插入的数小于mid对应的值，--mid，这样mid指向中间
• 如果插入的数大于mid的值，不动，这样mid指向中间

对于删除，我们每次删除的时候用set.erase(iter)，不能直接用int，否则所有相同的都会被删掉。所以我们用lower_bound()找，注意如果有duplicate的话，lower_bound会return最开头也就是最左边的。所以erase的时候：

• 如果当前长度为奇数
• 假设删除的数小于等于mid对应的值，++mid，mid指向中间较大的一个
• 假设删除的数大于mid对应的值，不动，mid指向中间较大的一个
• 如果当前长度为偶数
• 假设删除的数小于等于mid对应的值，++mid，这样mid指向中间
• 假设删除的数大于mid对应的值，不动，mid指向中间

这样我们可以一直保持mid的性质不变，时间复杂度O(n * log n)，代码如下：

双heap的做法依然是可行的，但是强烈不建议c++实现的用heap，因为c++的priority_queue不支持erase，所以我们可以用两个muliset做，整体还是类似的。时间复杂度O(n * log n)，代码如下：