用multiset的upper_bound/lower_bound优化你的LeetCode刷题：以‘数据流的中位数’和‘滑动窗口最大值’为例

用multiset的upper_bound/lower_bound优化你的LeetCode刷题：以‘数据流的中位数’和‘滑动窗口最大值’为例

在算法竞赛和面试刷题中，高效处理动态数据流和滑动窗口问题是常见的挑战。许多程序员在面对这类问题时，虽然知道可以使用multiset，但对于如何充分利用其upper_bound和lower_bound函数进行精准操作却感到困惑。本文将深入探讨这两个关键函数在解决"数据流的中位数"和"滑动窗口最大值"问题中的应用，提供可直接复用的C++代码模板和复杂度分析。

1. multiset基础与关键函数解析

multiset是C++ STL中一个强大的关联容器，它允许存储重复元素，并自动保持元素有序。与set不同，multiset可以包含多个相同值的元素，这使其特别适合处理需要维护有序序列且可能包含重复值的场景。

1.1 upper_bound与lower_bound的核心区别

这两个函数是multiset中最容易被混淆但又至关重要的成员函数：

multiset<int> ms = {1, 2, 2, 3, 4, 4, 4, 5}; auto lb = ms.lower_bound(3); // 指向第一个不小于3的元素 auto ub = ms.upper_bound(3); // 指向第一个大于3的元素

关键区别总结：

1.2 实际应用示例

考虑以下代码片段：

multiset<int> nums = {1, 3, 3, 5, 7}; cout << "Lower bound of 3: " << *nums.lower_bound(3) << endl; // 输出3 cout << "Upper bound of 3: " << *nums.upper_bound(3) << endl; // 输出5 cout << "Lower bound of 4: " << *nums.lower_bound(4) << endl; // 输出5 cout << "Upper bound of 4: " << *nums.upper_bound(4) << endl; // 输出5

注意：在使用这些函数返回的迭代器前，务必检查它是否等于end()，否则解引用可能导致未定义行为。

2. 数据流中位数问题的multiset解法

LeetCode 295题"数据流的中位数"要求设计一个数据结构，能够高效地添加数字并快速找出当前所有数字的中位数。传统解法使用两个堆（最大堆和最小堆），但multiset提供了更简洁的实现方式。

2.1 双指针维护中位数策略

利用multiset的有序特性，我们可以维护两个指针（或迭代器）来跟踪中位数位置：

class MedianFinder { private: multiset<int> data; multiset<int>::iterator left, right; public: MedianFinder() : left(data.end()), right(data.end()) {} void addNum(int num) { data.insert(num); if (data.size() == 1) { left = right = data.begin(); return; } if (data.size() % 2 == 0) { // 偶数大小 if (num >= *right) { left++; } else if (num < *left) { right--; } else { left++; right--; } } else { // 奇数大小 if (num >= *right) left = right; else if (num < *left) right = left; else { left++; right--; } } } double findMedian() { return (*left + *right) / 2.0; } };

2.2 复杂度分析

• 插入操作：O(log n) - multiset的插入操作
• 查找中位数：O(1) - 直接访问迭代器指向的值
• 空间复杂度：O(n) - 存储所有元素

提示：这种方法的优势在于代码简洁，且不需要像双堆解法那样手动平衡两个堆的大小。

3. 滑动窗口最大值问题的优化解法

LeetCode 480题"滑动窗口中位数"是295题的扩展，要求在滑动窗口中动态计算中位数。我们可以扩展上述方法，但需要更高效地处理元素的添加和删除。

3.1 滑动窗口维护策略

vector<double> medianSlidingWindow(vector<int>& nums, int k) { multiset<int> window(nums.begin(), nums.begin() + k); auto mid = next(window.begin(), k / 2); vector<double> medians; for (int i = k; ; i++) { // 计算当前窗口中位数 medians.push_back(k % 2 == 0 ? ((double)*mid + *prev(mid)) / 2 : *mid); if (i == nums.size()) break; // 插入新元素 window.insert(nums[i]); if (nums[i] < *mid) mid--; // 删除旧元素 if (nums[i - k] <= *mid) mid++; window.erase(window.lower_bound(nums[i - k])); } return medians; }

3.2 关键操作解析

1. 初始化窗口：用前k个元素填充multiset
2. 维护中位指针：始终指向中间或中间偏右的位置
3. 插入新元素：根据新元素值与当前中位数的关系调整指针
4. 删除旧元素：使用lower_bound精确定位要删除的元素

注意：在删除元素时，直接使用erase(value)会删除所有相同值的元素，而使用erase(iterator)则只删除指定的一个元素，这是处理重复元素时的关键区别。

4. 高级技巧与性能优化

4.1 自定义比较函数

multiset支持自定义排序规则，这在处理复杂数据结构时特别有用：

struct Point { int x, y; bool operator<(const Point& other) const { return x < other.x || (x == other.x && y < other.y); } }; multiset<Point> points;

4.2 批量操作与范围查询

利用lower_bound和upper_bound可以高效执行范围查询：

multiset<int> data = {1, 2, 2, 3, 4, 4, 4, 5}; // 查询[3,4]范围内的元素数量 auto low = data.lower_bound(3); auto high = data.upper_bound(4); int count = distance(low, high); // 返回5 (3,4,4,4)

4.3 性能对比：multiset vs 其他数据结构

从表中可以看出，multiset在需要频繁插入、删除和查询的场景下表现优异，特别是需要维护动态有序数据并快速访问中间值时。