Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector<double> result;
multiset<int> s(nums.begin(), nums.begin() + k);
multiset<int>::iterator it = next(s.begin(), k / 2);
for (int i = k;; ++i) {
if (k & 1)
result.push_back(*it);
else
result.push_back(((double)(*it) + *prev(it)) / 2);
if (i == nums.size())
break;
s.insert(nums[i]);
if (nums[i] < *it)
--it;
if (nums[i - k] <= *it)
++it;
s.erase(s.lower_bound(nums[i - k]));
}
return result;
}
};