LeetCode Solutions
480. Sliding Window Median
Time: $O((n - k + 1)\log k)$ Space: $O(k)$
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector<double> ans;
multiset<double> window(begin(nums), begin(nums) + k);
auto it = next(begin(window), (k - 1) / 2);
for (int i = k;; ++i) {
const double median = k & 1 ? *it : (*it + *next(it)) / 2.0;
ans.push_back(median);
if (i == nums.size())
break;
window.insert(nums[i]);
if (nums[i] < *it)
--it;
if (nums[i - k] <= *it)
++it;
window.erase(window.lower_bound(nums[i - k]));
}
return ans;
}
};