从一道LeetCode题出发，实战解析C++ set中lower_bound/upper_bound的四种经典用法

从一道LeetCode题出发，实战解析C++ set中lower_bound/upper_bound的四种经典用法

在算法面试和日常编程中，set容器的高效操作往往是解决问题的关键。lower_bound和upper_bound这两个函数虽然简单，但它们的组合使用却能解决许多复杂问题。本文将从一个具体LeetCode题目入手，逐步拆解四种经典应用场景，帮助读者掌握这一强大工具。

1. 理解基础：分界线思维

lower_bound和upper_bound的核心在于"分界线"概念。对于有序集合，这两个函数帮助我们快速定位虚拟的"分界线"位置：

• lower_bound(val): 返回第一个不小于val的元素迭代器
• upper_bound(val): 返回第一个大于val的元素迭代器

考虑一个简单的升序集合{1, 3, 5, 7, 9}：

set<int> s = {1, 3, 5, 7, 9}; auto lb = s.lower_bound(4); // 指向5 auto ub = s.upper_bound(4); // 同样指向5

有趣的是，当集合为降序时行为会变化：

set<int, greater<int>> s = {9, 7, 5, 3, 1}; auto lb = s.lower_bound(4); // 指向3 auto ub = s.upper_bound(4); // 同样指向3

注意：在降序集合中，lower_bound返回的是第一个不大于val的元素，这与升序时的逻辑正好相反。

2. 应用一：确定插入位置

LeetCode题目示例： 352. 将数据流变为多个不相交区间

问题场景：我们需要维护一个动态增长的数值集合，并在任何时候都能输出当前所有数值组成的不相交区间。

解决方案：使用set存储所有数字，利用lower_bound快速定位插入位置：

class SummaryRanges { private: set<int> nums; public: void addNum(int val) { nums.insert(val); } vector<vector<int>> getIntervals() { vector<vector<int>> res; if(nums.empty()) return res; auto start = nums.begin(); auto end = start; ++end; while(end != nums.end()) { if(*end != *start + 1) { res.push_back({*start, *start}); start = end; } ++end; } res.push_back({*start, *start}); return res; } };

优化点：在插入时使用lower_bound检查相邻元素：

void addNum(int val) { auto it = nums.lower_bound(val); if(it != nums.end() && *it == val) return; // 已存在 // 检查是否可以合并到前一个区间 if(it != nums.begin()) { auto prev = it; --prev; if(*prev + 1 == val) { nums.erase(prev); } } // 检查是否可以合并到后一个区间 if(it != nums.end() && *it == val + 1) { nums.erase(it); } nums.insert(val); }

3. 应用二：查找值域范围

LeetCode题目示例： 220. 存在重复元素 III

问题场景：判断数组中是否存在两个索引i和j，使得abs(nums[i]-nums[j]) <= t且abs(i-j) <= k。

解决方案：使用滑动窗口结合set的查找功能：

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { set<long> window; for(int i = 0; i < nums.size(); ++i) { if(i > k) { window.erase(nums[i-k-1]); } long num = nums[i]; auto lb = window.lower_bound(num - t); if(lb != window.end() && *lb <= num + t) { return true; } window.insert(num); } return false; }

关键点：

1. 维护一个大小为k的滑动窗口
2. 对于每个新元素，检查窗口中是否存在[num-t, num+t]范围内的值
3. lower_bound(num-t)快速定位范围起点

4. 应用三：实现滑动窗口逻辑

LeetCode题目示例： 480. 滑动窗口中位数

问题场景：计算滑动窗口中的中位数，窗口每次移动一位。

解决方案：使用两个set分别维护窗口的前后部分：

vector<double> medianSlidingWindow(vector<int>& nums, int k) { multiset<int> left, right; vector<double> res; for(int i = 0; i < nums.size(); ++i) { // 插入新元素 if(left.empty() || nums[i] <= *left.rbegin()) { left.insert(nums[i]); } else { right.insert(nums[i]); } // 平衡两个集合 if(left.size() > right.size() + 1) { right.insert(*left.rbegin()); left.erase(--left.end()); } else if(right.size() > left.size()) { left.insert(*right.begin()); right.erase(right.begin()); } // 计算中位数 if(i >= k - 1) { if(k % 2 == 1) { res.push_back(*left.rbegin()); } else { res.push_back(((double)*left.rbegin() + *right.begin()) / 2); } // 移除最左边的元素 int to_remove = nums[i - k + 1]; if(to_remove <= *left.rbegin()) { left.erase(left.find(to_remove)); } else { right.erase(right.find(to_remove)); } } } return res; }

优化技巧：

• 使用multiset允许重复元素
• 通过lower_bound快速定位要删除的元素
• 保持两个集合的大小差不超过1

5. 应用四：处理有序集合的区间合并与分割

LeetCode题目示例： 715. Range模块

问题场景：设计一个数据结构，能够高效地添加、删除和查询数值区间。

解决方案：使用set存储区间的端点，利用lower_bound快速定位相关区间：

class RangeModule { private: set<pair<int, int>> ranges; public: void addRange(int left, int right) { auto it = ranges.lower_bound({left, right}); // 合并左侧可能重叠的区间 if(it != ranges.begin()) { --it; if(it->second < left) { ++it; } else { left = min(left, it->first); right = max(right, it->second); ranges.erase(it++); } } // 合并右侧可能重叠的区间 while(it != ranges.end() && it->first <= right) { right = max(right, it->second); ranges.erase(it++); } ranges.insert({left, right}); } bool queryRange(int left, int right) { auto it = ranges.lower_bound({left, INT_MIN}); if(it != ranges.begin() && (--it)->second >= right) { return true; } return false; } void removeRange(int left, int right) { auto it = ranges.lower_bound({left, right}); // 处理左侧可能被分割的区间 if(it != ranges.begin()) { --it; if(it->second <= left) { ++it; } else { auto old = *it; ranges.erase(it); if(old.first < left) { ranges.insert({old.first, left}); } if(old.second > right) { ranges.insert({right, old.second}); } it = ranges.lower_bound({left, right}); } } // 处理完全包含在移除范围内的区间 while(it != ranges.end() && it->first < right) { if(it->second <= right) { ranges.erase(it++); } else { auto old = *it; ranges.erase(it); ranges.insert({right, old.second}); break; } } } };

关键操作：

1. addRange: 使用lower_bound找到插入位置，合并重叠区间
2. queryRange: 检查目标区间是否完全包含在某个现有区间内
3. removeRange: 分割被部分移除的区间

6. 高级技巧与性能对比

在实际应用中，lower_bound和upper_bound的性能表现优异，时间复杂度为O(log n)。以下是几种常见写法的性能对比：

代码优化示例：

// 不推荐的写法 auto it = lower_bound(s.begin(), s.end(), val); // O(n) // 推荐的写法 auto it = s.lower_bound(val); // O(log n)

特殊场景处理：

1. 自定义比较函数：当使用自定义排序规则时，需要确保比较逻辑与lower_bound一致

struct Point { int x, y; bool operator<(const Point& other) const { return x < other.x || (x == other.x && y < other.y); } }; set<Point> points; auto it = points.lower_bound({3, INT_MIN}); // 查找x>=3的第一个点

2. 多条件查询：结合多个lower_bound实现复杂查询

// 查找第一个满足a >= x && b >= y的元素 auto it = s.lower_bound({x, y}); while(it != s.end() && it->b < y) { ++it; }

3. 边界条件处理：总是检查返回值是否为end()

auto it = s.lower_bound(val); if(it == s.end()) { // 处理未找到的情况 } else { // 处理找到的情况 }

掌握这些高级技巧后，lower_bound和upper_bound将成为解决复杂算法问题的利器。在实际编码中，建议多思考"分界线"的概念，这能帮助更直观地理解这两个函数的行