0480. Sliding Window Median

题目信息

题号:

0480

难度:

Hard

主题:

连续窗口、中位数、奇偶长度、浮点结果

原题:

LeetCode 0480

重点:

窗口长度固定为 k、每次右移一位、偶数窗口取中间两数平均、按窗口顺序返回

题目重述

给定整数数组 nums 和整数 k,长度为 k 的连续窗口从数组最左端开始,每次向右移动一个位置,直到覆盖最后 k 个元素。返回每个窗口的中位数组成的数组。

把窗口元素排序后,若 k 为奇数,中位数是正中间的元素;若 k 为偶数,中位数是中间两个元素的算术平均值。nums.length 位于 [1, 10^5],元素在 32 位有符号整数范围内,k 位于 [1, nums.length]。答案允许 10^-5 以内的浮点误差。

自建示例

奇数长度窗口:

输入:nums = [2,1,4,7,2],k = 3
输出:[2.0,4.0,4.0]
解释:三个窗口排序后分别为 [1,2,4]、[1,4,7]、[2,4,7],中间值依次为 2、4、4。

偶数长度窗口:

输入:nums = [1,5,2,8],k = 2
输出:[3.0,3.5,5.0]
解释:每个窗口包含两个数,中位数分别是 (1+5)/2、(5+2)/2、(2+8)/2。

两个有序集合维护窗口中位位置

把当前窗口拆成 lower 和 upper 两个多重集合:lower 保存较小的一半,且最多比 upper 多一个元素;upper 保存较大的一半。每次加入或移除元素后,移动两个集合的边界元素恢复大小平衡,于是奇数窗口的中位数是 lower 最大值,偶数窗口的中位数是两边界的平均值。

使用 multiset 而不是 set,因为窗口中可能有重复数字;删除时只删除一个与待移出值相等的迭代器。插入新元素和移除旧元素都发生在窗口右移的同一轮。

C++ 实现

class Solution {
    std::multiset<long long> lower;
    std::multiset<long long> upper;

    void rebalance() {
        while (lower.size() > upper.size() + 1) {
            auto it = std::prev(lower.end());
            upper.insert(*it);
            lower.erase(it);
        }
        while (lower.size() < upper.size()) {
            auto it = upper.begin();
            lower.insert(*it);
            upper.erase(it);
        }
    }

    void add(long long value) {
        if (lower.empty() || value <= *lower.rbegin()) {
            lower.insert(value);
        } else {
            upper.insert(value);
        }
        rebalance();
    }

    void eraseValue(long long value) {
        auto lowerIt = lower.find(value);
        if (lowerIt != lower.end()) {
            lower.erase(lowerIt);
        } else {
            upper.erase(upper.find(value));
        }
        rebalance();
    }

    double median(int k) {
        if (k % 2 == 1) return static_cast<double>(*lower.rbegin());
        return (*lower.rbegin() + *upper.begin()) / 2.0;
    }

public:
    std::vector<double> medianSlidingWindow(std::vector<int>& nums, int k) {
        lower.clear();
        upper.clear();
        std::vector<double> result;
        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            add(nums[i]);
            if (i >= k) eraseValue(nums[i - k]);
            if (i >= k - 1) result.push_back(median(k));
        }
        return result;
    }
};

代码分析

平衡后 lower 的大小在奇数窗口时比 upper 多一、偶数窗口时相等,并且所有 lower 元素不大于所有 upper 元素,因此边界正好给出中位数。每个元素只插入和删除一次,时间复杂度为 O(n log k),额外空间复杂度为 O(k)。