用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：
- 若插入新长度（
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 {};</int></int></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 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></int>
}
// 使用示例
int main() {
std::vector
容易被忽略的边界和细节
路径还原依赖 prev 和 tail_idx 的严格同步，漏掉一次赋值就会断链。特别注意：
- 当
tail长度为 1 时，prev[i]应保持为-1（无前驱），不能误设 -
std::lower_bound是找「≥」，若需严格递增（不允许相等），应改用std::upper_bound并配合调整逻辑 - 输入含重复值时，LIS 定义决定行为——标准 LIS 要求严格递增，所以
[2,2]的 LIS 长度是 1，不是 2 - 还原路径时，
tail_idx存的是下标而非值，错当成值会导致越界或乱序
路径不唯一，算法输出的是按最后出现位置构造的一条可行解，不保证字典序最小或最大。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
