- 正确答案：该问题要求在求解最长递增子序列（LIS）长度的同时，能够重构出任意一个具体的LIS（如最靠前的、字典序最小的等），核心在于维护一个pre数组记录每个位置i在最优LIS路径中的前驱索引。最终通过反向遍历pre数组即可还原完整序列。 - 解答思路： 1. 首先明确标准LIS动态规划解法：dp[i]表示以nums[i]结尾的最长递增子序列长度，状态转移为 dp[i] = max{dp[j] + 1}，其中j < i且nums[j] < nums[i]；初始dp[i] = 1。 2. 为支持路径重构，在更新dp[i]时，同步记录pre[i] = j（即让dp[i]取得最大值的那个j）；若无满足条件的j，则pre[i] = -1（表示i是某条LIS的起点）。 3. 找到dp数组中最大值对应的位置idx（若有多个，取最后一个可得“最靠后”的LIS；若要字典序最小，需在状态转移时对j从左到右扫描并严格取第一个满足dp[j]+1==dp[i]且nums[j] dp[i]时才更新dp[i]和pre[i]（严格大于，确保取最早能扩展的j？不，这是错误理解——实际应是“>=”还是“>”取决于需求：若允许多个相同长度LIS，想取字典序最小的序列，则应在dp[j]+1 == dp[i]时比较nums[j]大小或j索引大小做稳定更新；但常规题默认取任意一个，故用>即可保证首次最优更新）。 - 更稳健写法：for j from 0 to i-1: if nums[j] < nums[i] and dp[j] + 1 > dp[i], then dp[i] = dp[j] + 1, pre[i] = j。 ● 路径还原的健壮性：由于pre构成有向无环图（DAG），且每个节点至多一个出边（pre[i]唯一），故从任意终点反向走必终止于pre[k]==-1，路径唯一。注意：可能存在多个等长LIS，pre只保存其中一条，由遍历j的顺序决定（如j升序扫描，则pre[i]取满足条件的**最大j**？不，是第一个使dp[j]+1最大的j；若多个j给出相同dp[j]+1，按循环顺序取第一个——因此j从0到i-1升序扫，得到的是“最左侧可接上的前驱”，对应LIS中较早出现的元素，有利于字典序较小（因nums[j]更小或索引更小）。 ● 进阶考点延伸： - 若要求所有LIS（数量统计）：需改用dp_count[i]表示以i结尾的LIS个数，转移时累加所有j满足dp[j]+1==dp[i]且nums[j] lengthOfLISWithPath(vector& nums) { int n = nums.size(); if (n == 0) return {}; vector dp(n, 1); vector pre(n, -1); // pre[i] = j means nums[j] is the previous element of nums[i] in some LIS // DP fill for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; pre[i] = j; } } } } // find the index with maximum dp value (last occurrence for stable tail) int max_len = 0, idx = -1; for (int i = 0; i < n; i++) { if (dp[i] > max_len) { max_len = dp[i]; idx = i; } } // reconstruct path backwards vector result; while (idx != -1) { result.push_back(nums[idx]); idx = pre[idx]; } reverse(result.begin(), result.end()); return result; } ``` - 补充说明（面试高频追问点）： Q：能否用O(n log n)时间同时得到LIS长度和一个具体序列？ A：标准二分法（维护tail数组+pos映射）只能得到长度；若强行重构，需额外维护每个nums[i]在tail中被哪个位置替代、以及该位置上一次是谁——这需要二维辅助结构（如prev_in_tail[i]记录i插入时覆盖的原索引，再配合parent链），实现复杂且非标准，通常面试中不作要求；O(n²) DP是预期解。 Q：pre数组会不会形成环？ A：不会。因为pre[i]只能指向j < i，索引严格递减，故路径必在有限步内到达-1。 Q：如果输入是[1,3,6,7,9,4,10]，手动模拟pre数组？ A：dp=[1,2,3,4,5,3,6], pre=[-1,0,1,2,3,0,4] → LIS为[1,3,6,7,9,10]（长度6），还原过程：idx=6→pre[6]=4→pre[4]=3→pre[3]=2→pre[2]=1→pre[1]=0→pre[0]=-1，对应nums[6,4,3,2,1,0] = [10,9,7,6,3,1]，逆序后即[1,3,6,7,9,10]。

26校招美团推荐算法一面

全站热榜

创作者周榜