LeetCode 480. 滑动窗口中位数
原题链接
困难
作者:
MZZDX
,
2023-03-21 13:27:37
,
所有人可见
,
阅读 201
class Solution
{
private:
vector<double> res;
multiset<long long> up;
multiset<long long, greater<long long>> down;
double get_val()
{
if ((up.size() + down.size()) & 1) return *down.begin();
return (*down.begin() + *up.begin()) / 2.0;
}
void adjust()
{
while (down.size() > up.size() + 1)
{
up.insert(*down.begin()), down.erase(down.begin());
}
while (up.size() > down.size())
{
down.insert(*up.begin()), up.erase(up.begin());
}
}
void remove(long long num)
{
auto it1 = down.find(num);
if (it1 != down.end())
{
down.erase(it1), adjust();
return;
}
auto it2 = up.find(num);
if (it2 != up.end())
{
up.erase(it2), adjust();
return;
}
}
void push(long long num)
{
if (down.empty() || num <= *down.begin()) down.insert(num);
else up.insert(num);
adjust();
}
public:
vector<double> medianSlidingWindow(vector<int> &nums, int k)
{
deque<int> q;
for (int i = 0; i < nums.size(); ++i)
{
if (i >= k) remove(q.front()), q.pop_front();
q.push_back(nums[i]), push(nums[i]);
if (i >= k - 1) res.push_back(get_val());
}
return res;
}
};