最长递增子序列（Longest Increasing Subsequence, LIS）是算法面试中的高频题目：给定一个整数数组，找到其中最长的严格递增子序列的长度。经典的动态规划解法是 O(n²)，但通过patience sorting（耐心排序）思想结合二分查找，可以将复杂度优化到 O(n log n)。本文将用Java实现两种解法，并讲解如何还原实际的子序列路径。
一、问题定义
输入: [10, 9, 2, 5, 3, 7, 101, 18]
输出: 4
解释: 最长递增子序列是 [2, 3, 7, 101]
二、O(n²) 动态规划解法
2.1 状态定义
dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
2.2 状态转移
对于每个位置 i，遍历所有 j < i：
– 若 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)
2.3 Java 实现
public class LIS {
// O(n²) 解法
public static int lengthOfLIS_DP(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1); // 每个元素本身构成长度为1的LIS
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
}
三、O(n log n) Patience Sorting 解法
3.1 核心思想
想象在玩纸牌游戏”耐心排序”：将数字视为纸牌，从左到右依次处理。维护若干堆（pile），规则是：
– 每张新牌放在最左边牌顶 ≥ 该牌的堆上
– 如果没有这样的堆，新建一堆放在最右边
关键性质：堆的数量等于 LIS 的长度。通过二分查找可以在 O(log n) 时间内确定每张牌放入哪个堆。
3.2 优化数组的设计
我们用一个数组 tails 记录每堆的顶部牌面，tails[i] 表示长度为 i+1 的递增子序列的最小结尾元素。
// O(n log n) 解法
public static int lengthOfLIS_BinarySearch(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] tails = new int[n];
int size = 0;
for (int num : nums) {
// 二分查找：找到 tails 中第一个 >= num 的位置
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
if (left == size) {
size++; // 新建一堆
}
}
return size;
}
3.3 算法执行 trace
以 [10, 9, 2, 5, 3, 7, 101, 18] 为例：
| 步骤 | 当前数字 | tails 数组 | 操作 |
|---|---|---|---|
| 1 | 10 | [10] | 新建堆 |
| 2 | 9 | [9] | 替换堆顶 |
| 3 | 2 | [2] | 替换堆顶 |
| 4 | 5 | [2, 5] | 新建堆 |
| 5 | 3 | [2, 3] | 替换第2堆 |
| 6 | 7 | [2, 3, 7] | 新建堆 |
| 7 | 101 | [2, 3, 7, 101] | 新建堆 |
| 8 | 18 | [2, 3, 7, 18] | 替换第4堆 |
最终 size = 4，即 LIS 长度。
四、还原实际子序列路径
上述方法只求出了长度，如何还原具体的子序列？需要额外记录前驱信息和每个长度对应的结尾元素位置。
public static List<Integer> getLIS(int[] nums) {
if (nums == null || nums.length == 0) return Collections.emptyList();
int n = nums.length;
int[] tails = new int[n]; // tails[i] = 长度为i+1的LIS的最小结尾元素的索引
int[] prev = new int[n]; // prev[i] = nums[i]在LIS中的前一个元素的索引
Arrays.fill(prev, -1);
int size = 0;
for (int i = 0; i < n; i++) {
// 二分查找
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[tails[mid]] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
// 记录前驱
if (left > 0) {
prev[i] = tails[left - 1];
}
tails[left] = i;
if (left == size) {
size++;
}
}
// 从最后一个元素反向回溯
List<Integer> lis = new ArrayList<>();
int k = tails[size - 1];
while (k >= 0) {
lis.add(nums[k]);
k = prev[k];
}
Collections.reverse(lis);
return lis;
}
五、最长递减子序列与变形
通过简单修改比较符号，可以求解：
– 最长递减子序列：将 < 改为 >
– 最长非递减子序列：将 < 改为 <=
– 最长连续递增子序列：去掉二分查找，只比较相邻元素
// 最长递减子序列（通过反转比较）
public static int lengthOfLDS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int num : nums) {
int left = 0, right = size;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] > num) { // 注意这里是 >
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
if (left == size) size++;
}
return size;
}
六、应用场景
LIS 及其变种在多个领域有重要应用：
– 俄罗斯套娃信封问题：二维LIS
– 最长摆动子序列：交替增减
– 最大不相交区间集：按结束时间排序后求LIS
– ** patience sorting 与卡牌游戏**： piles 数量与 LIS 的对偶关系
七、复杂度总结
| 方法 | 时间复杂度 | 空间复杂度 | 能否还原路径 |
|---|---|---|---|
| DP | O(n²) | O(n) | 可以 |
| Patience Sorting + 二分 | O(n log n) | O(n) | 可以 |
八、总结
最长递增子序列问题完美展示了算法优化的经典路径：从直观的 O(n²) 动态规划，到利用二分查找将内层循环优化为对数时间，最终达到 O(n log n)。patience sorting 的视角不仅提供了优雅的实现方式，更揭示了组合数学中偏序集与Dilworth定理的深刻联系——最大反链的大小等于最小链覆盖数。
