Почему это работает
- Число попадает в low, только если оно не больше верха low, а переносятся числа только с верхов. Поэтому всё в low не больше всего в high.
- После каждого addNum в low столько же чисел, сколько в high, или на одно больше. Значит, середина отсортированных чисел — прямо на верхах: верх low или среднее двух верхов.
- По 5 видно, зачем нужны оба переноса: 1 выводит low вперёд на два, и 5 уходит в high; 9 выводит вперёд high, и 5 возвращается.
Сложность
addNum: время O(log n), не больше двух добавлений и одного удаления. findMedian: время O(1), он только читает верхи. Память O(n) на все числа.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗