人麻了，领导让我写个脚本，把数据库700T数据，全部迁移到别的机房，带宽不超过2Mbps。。。

不得不说，写算法题的时候，我总是有点上头，尤其是遇到“滑动窗口中位数”这种题。看着它，脑子里就两个字：头大。可是程序员嘛，头再大也得硬上，不然吃啥饭？

这题咋说呢，经典滑动窗口题目，给你一个整数数组，和一个窗口大小k，窗口从左往右滑，每次滑的时候，窗口里的数能组成一个子数组，你得求每个子数组的中位数。听着好像不难，滑动窗口谁不会？可关键是求中位数这件事，稍微一想，咦，复杂度不太对劲啊。

咱们普通求中位数，咋搞？排序呗，中间那个数就是中位数。如果窗口每滑一次都排序，那时间复杂度就是O(k log k)，整个数组滑一遍下来，O(n k log k)，这规模一大，直接TLE（超时）警告。

怎么办？还得优化。这里就有点意思了，要实时维护一个滑动窗口内的中位数，优先队列（堆）这东西不能少。咱们来点骚操作：用两个堆——一个大顶堆，一个小顶堆。大顶堆存窗口中较小的一半元素，小顶堆存窗口中较大的一半元素。这样，中位数就在两个堆顶上，窗口是奇数个的时候，取大顶堆堆顶就行，窗口是偶数个，取两个堆顶的平均数。

讲起来简单，实现起来真不一定，这里面有几个坑：

1. 1. Java的PriorityQueue默认是小顶堆，想要大顶堆得反着搞；
2. 2. 堆里不能直接删某个元素，想删只能遍历——这不行，性能拉垮；
3. 3. 怎么平衡两个堆的大小，保证它们数量差不超过1。

咱们程序员的通病，就是喜欢抠细节。我写这题的时候，想了下，堆删除不方便，直接搞两个TreeSet更香，底层红黑树，增删查都是O(log k)，还能存重复元素的索引，完美解决。

来，代码伺候：

classSolution {
publicdouble[] medianSlidingWindow(int[] nums, int k) {
        TreeSet<Integer> left = newTreeSet<>((a, b) -> nums[a] == nums[b] ? a - b : Integer.compare(nums[b], nums[a]));
        TreeSet<Integer> right = newTreeSet<>((a, b) -> nums[a] == nums[b] ? a - b : Integer.compare(nums[a], nums[b]));

double[] res = newdouble[nums.length - k + 1];
for (inti=0; i < nums.length; i++) {
if (left.size() <= right.size()) {
                left.add(i);
if (!right.isEmpty() && nums[left.first()] > nums[right.first()]) {
intl= left.pollFirst();
intr= right.pollFirst();
                    left.add(r);
                    right.add(l);
                }
            } else {
                right.add(i);
if (nums[left.first()] > nums[right.first()]) {
intl= left.pollFirst();
intr= right.pollFirst();
                    left.add(r);
                    right.add(l);
                }
            }
if (i >= k - 1) {
if (k % 2 == 1) {
                    res[i - k + 1] = nums[left.first()];
                } else {
                    res[i - k + 1] = ((long)nums[left.first()] + nums[right.first()]) / 2.0;
                }
inttoRemove= i - k + 1;
if (!left.remove(toRemove)) {
                    right.remove(toRemove);
                }
            }
        }
return res;
    }
}

写完这段代码，我有点小满足，这就像调好了一个小型系统，两个红黑树平衡得稳稳的，谁动了谁就被调整。中位数？分分钟给你算出来。

不过，这题给我最大的感悟，还是别小瞧数据结构。写业务代码的时候，总想着简单直接，能跑就行，但刷算法题，真的是让人重新认识底层这些玩意。红黑树、堆这些看着没啥用的东西，关键时刻真的救命。就像平时看着不起眼的键盘快捷键，真要写代码赶工的时候，那速度，快得跟开挂一样。

所以啊，程序员还是得多刷刷题，不光是为了应付面试，这些技巧说不定哪天在项目里也能用得上。再说了，解决了一个难题之后的成就感，嘿，真的爽！