LeetCode 补充题 138. 字典序最小的最长递增子序列
题目描述
[!green]
牛客原题： ✅ 补充题 138. 字典序最小的最长递增子序列
给你一个整数数组
nums，请返回一条最长严格递增子序列。如果存在多条最长结果，返回按整数值比较时字典序最小的一条。子序列可以跳过元素，但不能改变原来的相对顺序。空数组返回空数组。
示例 1：
输入：
nums = [2,1,5,3,6,4,8,9,7]
输出：[1,3,4,8,9]
解释： 最长长度为 5；在所有长度为 5 的递增子序列中，该序列的字典序最小。
示例 2：
输入：
nums = [1,2,8,6,4]
输出：[1,2,4]
解释： 最长长度为 3，第三个元素取 4 比取 6 或 8 的字典序更小。
提示：
0 <= n <= 2000000 <= arr[i] <= 1000000000
题意分析
只求最长长度时，维护每种长度的最小结尾即可；但这些结尾可能来自不相容的位置，不能直接拼成原数组中的子序列。本题还要求字典序最小的实际结果，因此同时记录每个位置的结尾 LIS 长度，再按原下标恢复。
解法：tails 层号与逆序恢复最小 LIS
核心思路
[!blue]
先分清两个数组：
tails[t - 1]是长度为t的递增子序列的最小结尾值；lengths[i]是必须以nums[i]结尾时的 LIS 长度。前者用于二分求长度，后者用于在原数组中恢复真实序列，不能把最终tails直接作为答案。恢复时，从右向左依次寻找
lengths[i] == L、L - 1、…、1的位置。为什么选择同层最靠右的候选：
- 同一层的值按下标顺序不可能严格增大。否则较大的后项可以接在前项后面，它的 LIS 长度就至少多一层，产生矛盾。因此同层越靠右，值不会更大。
- 已选第
t层节点的左侧一定有合法的第t - 1层前驱。该层最靠右的候选不大于这个前驱，所以仍小于已选值，能继续连接；这就是代码不额外比较相邻结果值的原因。- 任意最长序列的第
t项，其结尾 LIS 长度都恰为t。倒序选择最靠右候选，使每层取到的值不大于其他最长结果在该层的值，因而得到字典序最小的结果。例如
[3,1,2,4]的lengths为[1,1,2,3]，从右到左选取长度为3、2、1的节点，逆向填入结果后得到[1,2,4]。
解题步骤
- 为当前值
x二分查找tails中第一个大于等于它的位置l。前l层的结尾严格小于x，当前结尾长度便是l + 1。- 用
x更新该层的最小结尾；如果l == size，最长长度增加 1。将当前层号保存到lengths[i]。- 分配长度为
size的结果数组，从右向左寻找层号依次为size、size-1、…、1的位置。- 每找到一项，就从结果末尾向前填入并降低所需层号；空输入直接得到空数组。
代码实现
class Solution {
public int[] lis(int[] nums) {
int n = nums.length;
int size = 0;
int[] tails = new int[n];
int[] lengths = new int[n];
for (int i = 0; i < n; i++) {
int l = 0;
int r = size;
while (l < r) {
int mid = (l + r) >>> 1;
if (tails[mid] < nums[i]) {
l = mid + 1;
} else {
r = mid;
}
}
tails[l] = nums[i];
if (l == size) {
size++;
}
lengths[i] = l + 1;
}
int[] result = new int[size];
for (int i = n - 1, need = size; i >= 0 && need > 0; i--) {
if (lengths[i] == need) {
result[--need] = nums[i];
}
}
return result;
}
}
func lis(nums []int) []int {
tails := make([]int, len(nums))
lengths := make([]int, len(nums))
size := 0
for i, x := range nums {
l, r := 0, size
for l < r {
mid := (l + r) / 2
if tails[mid] < x {
l = mid + 1
} else {
r = mid
}
}
tails[l] = x
if l == size {
size++
}
lengths[i] = l + 1
}
result := make([]int, size)
for i, need := len(nums)-1, size; i >= 0 && need > 0; i-- {
if lengths[i] == need {
need--
result[need] = nums[i]
}
}
return result
}
复杂度分析
- 时间复杂度：$O(n \log n)$。
- 空间复杂度：额外空间 $O(n)$。
关键点总结
[!green]
任意最长序列的第t项，其结尾LIS长度必为t，否则能够拼出更长序列。同层候选值随下标非增，倒序取最靠右的位置得到较小值。
易错点总结
[!yellow]
二分找第一个大于等于 x 的位置，重复值不能延长严格上升序列；tails 不是最终序列；字典序按整数值比较。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 长度算法还需记录每个位置的层号，tails 本身并非一条可直接返回的原序列。 |
| 673. 最长递增子序列的个数 | 中等 | 同样在 LIS 长度之外保存信息，原题保存方案数，本题保存层号以恢复满足字典序的实际序列。 |