用std::lower_bound求LIS长度为O(n log n)，核心是维护tail数组存各长度递增子序列的最小末尾；还原路径需额外记录prev和tail_idx数组，从tail_idx末尾沿prev反向追踪并反转即得一条合法LIS。
用 std::lower_bound 实现 O(n log n) LIS 长度计算
直接求长度不难，关键是避免 O(n²) 的朴素 DP。核心是维护一个「当前能构成的最短递增末尾数组」：tail[i] 表示长度为 i+1 的递增子序列中最小的末尾值。遍历每个数 x，用 std::lower_bound 找到第一个 ≥ x 的位置并替换——这保证了 tail 始终单调递增，且每步更新都保持最优性。
注意：这个过程只得到长度，tail 数组本身不是解路径，不能直接输出。
-
tail初始为空，对每个x，auto it = std::lower_bound(tail.begin(), tail.end(), x) - 若
it == tail.end()，则tail.push_back(x)；否则*it = x - 最终
tail.size()就是 LIS 长度
如何反向还原 LIS 路径（关键难点）
仅靠 tail 无法还原路径，必须在正向扫描时额外记录每个位置的「前驱索引」。常见错误是试图从 tail 逆推，但 tail 中的值可能来自不同原始位置，且被多次覆盖。
正确做法：开两个辅助数组：prev[i] 存位置 i 在 LIS 中的前一个元素下标，tail_idx[i] 存长度为 i+1 的子序列末尾在原数组中的真实下标。每次在 tail 中更新某个位置时，同步更新 tail_idx 和 prev：
立即学习“C++免费学习笔记（深入）”；
- 若插入新长度（
it == tail.end()），则prev[i] = tail_idx.back()（上一长度末尾） - 否则，
prev[i] = tail_idx[it - tail.begin() - 1]（前一长度末尾） - 同时更新
tail_idx[it - tail.begin()] = i
最后从 tail_idx.back() 开始，沿 prev 链表倒推即可得路径。
完整可运行示例（含路径打印）
#include <vector>
#include <algorithm>
#include <iostream>
<p>std::vector<int> lis_with_path(const std::vector<int>& nums) {
if (nums.empty()) return {};</p><pre class='brush:php;toolbar:false;'>int n = nums.size();
std::vector<int> tail, tail_idx, prev(n, -1);
for (int i = 0; i < n; ++i) {
auto it = std::lower_bound(tail.begin(), tail.end(), nums[i]);
int pos = it - tail.begin();
if (it == tail.end()) {
tail.push_back(nums[i]);
if (!tail_idx.empty()) {
prev[i] = tail_idx.back();
}
tail_idx.push_back(i);
} else {
*it = nums[i];
tail_idx[pos] = i;
if (pos > 0) {
prev[i] = tail_idx[pos - 1];
}
}
}
// 反向构造路径
std::vector<int> path;
int cur = tail_idx.back();
while (cur != -1) {
path.push_back(nums[cur]);
cur = prev[cur];
}
std::reverse(path.begin(), path.end());
return path;}
// 使用示例
int main() {
std::vector 路径还原依赖 路径不唯一，算法输出的是按最后出现位置构造的一条可行解，不保证字典序最小或最大。容易被忽略的边界和细节
prev 和 tail_idx 的严格同步，漏掉一次赋值就会断链。特别注意：
tail 长度为 1 时，prev[i] 应保持为 -1（无前驱），不能误设std::lower_bound 是找「≥」，若需严格递增（不允许相等），应改用 std::upper_bound 并配合调整逻辑[2,2] 的 LIS 长度是 1，不是 2tail_idx 存的是下标而非值，错当成值会导致越界或乱序
