企业官网建设流程全解析

二分库函数 ranges::lower_bound

ranges::lower_bound是C++20引入的<algorithm>库中的函数，它是传统std::lower_bound的现代升级版。

别被名字吓到，它的核心功能非常简单：在一个有序序列中，二分查找第一个“大于等于”目标值的位置。

1. 最直观的对比

假设你有一个严格递增数组g = [2, 4, 6, 8]，你要找x = 5：

// ✅ C++20 新写法（简洁、安全）autoit=ranges::lower_bound(g,5);// it 指向 6（第一个 >= 5 的元素）// ❌ C++17 旧写法（冗长、易错）autoit=std::lower_bound(g.begin(),g.end(),5);// 效果完全相同，但要手写 begin/end

如果x = 9（比所有元素都大），it == g.end()，表示没找到。

2. 在 LIS 中的完整用法

回到你之前的代码，逐行拆解：

vector<int>g;// g 始终保持严格递增for(intx:nums){// 🔍 在 g 中二分查找第一个 >= x 的位置autoit=ranges::lower_bound(g,x);if(it==g.end()){// x 比 g 中所有元素都大 → LIS 可以延长g.push_back(x);}else{// 找到了 >= x 的元素 → 用更小的 x 替换它// 这样未来有更多机会延长 LIS*it=x;}}returng.size();// g 的长度就是 LIS 长度

3. 为什么叫 “lower_bound”？

这个名字来源于数学概念：

记忆口诀：

• Lower= ≥ （下界，包含自身）
• Upper= > （上界，不包含自身）

在严格递增 LIS中，我们用lower_bound（因为相等元素不能延长 LIS，需要替换）。如果题目改为非递减 LIS，则改用upper_bound。

4. 相比旧版std::lower_bound的优势

💡 投影功能（高级但实用）

structStudent{intscore;string name;};vector<Student>students={{90,"A"},{80,"B"},{70,"C"}};// 按 score 排序后，直接按 score 字段二分查找autoit=ranges::lower_bound(students,85,{},&Student::score);// 无需写 lambda，第三个参数 {} 表示默认比较，第四个是投影

5. ⚠️ 面试注意事项

📌 一句话总结

ranges::lower_bound(container, value)= 在有序容器中二分找第一个 ≥ value 的位置。它就是std::lower_bound的语法糖 + 安全加固版，LIS 中用它来维护贪心数组，把O ( N 2 ) O(N^2)O(N2)优化到O ( N log ⁡ N ) O(N \log N)O(NlogN)。

如果你当前环境不支持 C++20，记住等价替换即可，逻辑完全一致：

// C++20autoit=ranges::lower_bound(g,x);// C++17 及以下（完全等价）autoit=lower_bound(g.begin(),g.end(),x);

Lower = ≥ （下界）
Upper = > （上界）
想要 < → 用 lower_bound 然后 -1
想要 ≤ → 用 upper_bound 然后 -1
永远记得检查边界（it == begin() 时减一会越界！）

捕获 lambda【&】

在 C++ 的 Lambda 表达式中，[]里的内容叫做捕获列表（Capture List），它决定了 Lambda 如何访问外部作用域的变量。

[&]的意思是：按引用（by reference）捕获外部所有自动存储期变量。

1. 三种最常见的捕获方式对比

inta=10;intb=20;// ✅ [&] 按引用捕获所有外部变量autof1=[&](){a++;};// 修改的是外部的 af1();cout<<a;// 输出 11 ← 外部 a 被改了// ✅ [=] 按值（拷贝）捕获所有外部变量autof2=[=]()mutable{a++;};// 修改的是内部副本f2();cout<<a;// 输出 10 ← 外部 a 不变// ✅ [&ls] 只按引用捕获 ls，其他变量不可访问autof3=[&ls](intx){...};// 精确控制，面试推荐

2. 用一张表记住

3. 为什么面试建议用[&ls]而非[&]？

回到你的 LIS 代码：

// ❌ [&] —— 捕获了 nums, n, i, findindex 等所有变量// 面试官会想："你真的需要捕获这么多吗？还是只是懒得写？"autofindindex=[&](intx)->int{...};// ✅ [&ls] —— 只捕获了二分查找真正需要的数组// 面试官看到就知道：你清楚这个 lambda 只依赖 lsautofindIndex=[&ls](intx)->int{...};

核心区别不是功能，而是表达力：显式捕获 = 告诉面试官"我思考过这个 Lambda 的数据依赖边界"。

4. ⚠️[&]的经典坑

vector<function<int()>>funcs;for(inti=0;i<5;i++){funcs.push_back([&](){returni;});// 💥 按引用捕获了循环变量 i}for(auto&f:funcs)cout<<f()<<" ";// 输出：5 5 5 5 5 （全是 5！因为 i 已经变成 5 了）

如果改成[i]（按值捕获），每个 Lambda 会保存自己那份i的副本，输出就是0 1 2 3 4。

📌 一句话总结

[&]= “把外面所有变量都借进来用（可改）”
[&ls]= “我只借ls这一个变量来用”

功能上[&]没问题，但面试中写[&ls]是在展示你对数据流的精确掌控。