Patience Sorting（耐心排序）的最长递增子序列（LIS）应用与优化策略

字数 2334 2025-12-06 15:30:20

Patience Sorting（耐心排序）的最长递增子序列（LIS）应用与优化策略

题目描述
给定一个整数数组 nums，请找出其最长递增子序列（Longest Increasing Subsequence, LIS）的长度。子序列是指从原数组中保持相对顺序取出若干元素（可以不连续），且元素单调递增的序列。要求时间复杂度尽可能低。

例如：
输入：nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出：4
解释：最长递增子序列是 [2, 5, 7, 101] 或 [2, 5, 7, 18]，长度均为 4。

解题过程

1. 问题理解与朴素解法
最长递增子序列（LIS）是一个经典动态规划（DP）问题。最直观的 DP 解法是：

定义 dp[i] 为以第 i 个元素结尾的 LIS 长度。
状态转移：dp[i] = 1 + max(dp[j])，其中 0 ≤ j < i 且 nums[j] < nums[i]。
最终答案是 max(dp)。
时间复杂度为 O(n²)，空间复杂度为 O(n)。
但当数组长度 n 很大时（例如 n=10⁵），平方复杂度不可接受，需要更优的算法。

2. Patience Sorting 的引入
Patience Sorting 本是一种基于“纸牌游戏”的排序算法，但其核心思想可以直接用于求解 LIS 长度，且时间复杂度可达 O(n log n)。
核心步骤模仿“接龙游戏”：

从数组从左到右处理每个数字，看作一张张纸牌。
规则：将当前数字放入最左侧的、堆顶（即该堆最小元素）≥ 当前数字的堆中；若没有这样的堆，则新建一个堆放在最右侧。
最终堆的数量就是 LIS 的长度。

为什么这能求出 LIS 长度？
直观解释：每个堆维护一个“递增子序列”，堆顶递增；堆的数量表示当前能找到的不相交的递增子序列的最小数量。Dilworth 定理的一个推论是：最小链划分的大小等于最长反链的长度，在这里等价于“堆数 = 最长递增子序列的长度”。更易懂的理解是：堆的数量恰好等于最长递增子序列的长度，因为每次建新堆意味着当前元素比所有堆顶都大，可以延长 LIS。

3. 具体步骤模拟
以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例：

初始化一个空数组 piles 表示堆顶元素列表：

数字 10：没有堆，新建堆 → piles = [10]
数字 9：找到第一个 ≥9 的堆顶是 10，替换为 9 → piles = [9]
数字 2：找到第一个 ≥2 的堆顶是 9，替换为 2 → piles = [2]
数字 5：堆顶 2 < 5，没有 ≥5 的堆顶，新建堆 → piles = [2, 5]
数字 3：找到第一个 ≥3 的堆顶是 5，替换为 3 → piles = [2, 3]
数字 7：堆顶 3 < 7，没有 ≥7 的堆顶，新建堆 → piles = [2, 3, 7]
数字 101：堆顶 7 < 101，新建堆 → piles = [2, 3, 7, 101]
数字 18：找到第一个 ≥18 的堆顶是 101，替换为 18 → piles = [2, 3, 7, 18]

最终堆的数量为 4，即 LIS 长度。注意 piles 本身并不一定是 LIS 的具体序列，但它记录了堆顶的递增序列，可用于重构 LIS。

4. 实现优化：二分查找
在“找到第一个 ≥ 当前数字的堆顶”时，由于 piles 始终是递增的（因为每次放数字要么替换某个堆顶，要么新建堆放在末尾，不会破坏有序性），所以可以用二分查找快速定位插入位置。

算法伪代码：

piles = []  // 记录堆顶
for each num in nums:
    idx = lower_bound(piles, num)  // 第一个 ≥ num 的位置
    if idx == piles.size:
        piles.append(num)  // 新建堆
    else:
        piles[idx] = num  // 替换堆顶
return piles.size

这里 lower_bound 是二分查找，时间复杂度 O(log n)。整体时间复杂度为 O(n log n)，空间复杂度 O(n)。

5. 重构 LIS 序列
如果题目要求输出具体的 LIS 序列，可以在上述过程中额外记录信息。
方法：维护一个 prev 数组，记录每个数字在“其所在堆的前一个堆的堆顶元素索引”。具体步骤：

用数组 piles_val 记录每个堆的堆顶值。
用数组 piles_idx 记录每个堆顶在 nums 中的索引。
用 prev[i] 记录 nums[i] 在 LIS 中的前驱索引（初始化为 -1）。
当用 num 替换第 idx 堆的堆顶时，设置 prev[当前索引] = (idx>0 ? piles_idx[idx-1] : -1)。
最后从最后一个堆的堆顶索引反向追踪，即可得到 LIS。

6. 时间复杂度与空间复杂度

时间复杂度：O(n log n)，因为每个数字一次二分查找。
空间复杂度：O(n)，存储 piles 和可能的 prev 数组。

7. 举例验证
用 nums = [3, 4, 1, 2, 5] 演示：

3 → [3]
4 → [3, 4]
1 → 替换 3 → [1, 4]
2 → 替换 4 → [1, 2]
5 → 新建 → [1, 2, 5]
堆数为 3，LIS 长度 3，序列为 [3,4,5] 或 [1,2,5]。注意算法得到的是长度，具体序列取决于追踪方式。

8. 总结
Patience Sorting 在求解 LIS 长度问题上，将时间复杂度从 O(n²) 优化到 O(n log n)，其核心是维护堆顶数组并利用二分查找。该算法也体现了“贪心 + 二分”的思想，是解决 LIS 问题的标准高效算法。

Patience Sorting（耐心排序）的最长递增子序列（LIS）应用与优化策略题目描述给定一个整数数组 nums ，请找出其最长递增子序列（Longest Increasing Subsequence, LIS）的长度。子序列是指从原数组中保持相对顺序取出若干元素（可以不连续），且元素单调递增的序列。要求时间复杂度尽可能低。例如：输入： nums = [10, 9, 2, 5, 3, 7, 101, 18] 输出：4 解释：最长递增子序列是 [2, 5, 7, 101] 或 [2, 5, 7, 18] ，长度均为 4。解题过程 1. 问题理解与朴素解法最长递增子序列（LIS）是一个经典动态规划（DP）问题。最直观的 DP 解法是：定义 dp[i] 为以第 i 个元素结尾的 LIS 长度。状态转移： dp[i] = 1 + max(dp[j]) ，其中 0 ≤ j < i 且 nums[j] < nums[i] 。最终答案是 max(dp) 。时间复杂度为 O(n²)，空间复杂度为 O(n)。但当数组长度 n 很大时（例如 n=10⁵），平方复杂度不可接受，需要更优的算法。 2. Patience Sorting 的引入 Patience Sorting 本是一种基于“纸牌游戏”的排序算法，但其核心思想可以直接用于求解 LIS 长度，且时间复杂度可达 O(n log n)。核心步骤模仿“接龙游戏”：从数组从左到右处理每个数字，看作一张张纸牌。规则：将当前数字放入最左侧的、堆顶（即该堆最小元素）≥ 当前数字的堆中；若没有这样的堆，则新建一个堆放在最右侧。最终堆的数量就是 LIS 的长度。为什么这能求出 LIS 长度？直观解释：每个堆维护一个“递增子序列”，堆顶递增；堆的数量表示当前能找到的不相交的递增子序列的最小数量。Dilworth 定理的一个推论是：最小链划分的大小等于最长反链的长度，在这里等价于“堆数 = 最长递增子序列的长度”。更易懂的理解是：堆的数量恰好等于最长递增子序列的长度，因为每次建新堆意味着当前元素比所有堆顶都大，可以延长 LIS。 3. 具体步骤模拟以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例：初始化一个空数组 piles 表示堆顶元素列表：数字 10：没有堆，新建堆 → piles = [10] 数字 9：找到第一个 ≥9 的堆顶是 10，替换为 9 → piles = [9] 数字 2：找到第一个 ≥2 的堆顶是 9，替换为 2 → piles = [2] 数字 5：堆顶 2 < 5，没有 ≥5 的堆顶，新建堆 → piles = [2, 5] 数字 3：找到第一个 ≥3 的堆顶是 5，替换为 3 → piles = [2, 3] 数字 7：堆顶 3 < 7，没有 ≥7 的堆顶，新建堆 → piles = [2, 3, 7] 数字 101：堆顶 7 < 101，新建堆 → piles = [2, 3, 7, 101] 数字 18：找到第一个 ≥18 的堆顶是 101，替换为 18 → piles = [2, 3, 7, 18] 最终堆的数量为 4，即 LIS 长度。注意 piles 本身并不一定是 LIS 的具体序列，但它记录了堆顶的递增序列，可用于重构 LIS。 4. 实现优化：二分查找在“找到第一个 ≥ 当前数字的堆顶”时，由于 piles 始终是递增的（因为每次放数字要么替换某个堆顶，要么新建堆放在末尾，不会破坏有序性），所以可以用二分查找快速定位插入位置。算法伪代码：这里 lower_bound 是二分查找，时间复杂度 O(log n)。整体时间复杂度为 O(n log n)，空间复杂度 O(n)。 5. 重构 LIS 序列如果题目要求输出具体的 LIS 序列，可以在上述过程中额外记录信息。方法：维护一个 prev 数组，记录每个数字在“其所在堆的前一个堆的堆顶元素索引”。具体步骤：用数组 piles_val 记录每个堆的堆顶值。用数组 piles_idx 记录每个堆顶在 nums 中的索引。用 prev[i] 记录 nums[i] 在 LIS 中的前驱索引（初始化为 -1）。当用 num 替换第 idx 堆的堆顶时，设置 prev[当前索引] = (idx>0 ? piles_idx[idx-1] : -1) 。最后从最后一个堆的堆顶索引反向追踪，即可得到 LIS。 6. 时间复杂度与空间复杂度时间复杂度：O(n log n)，因为每个数字一次二分查找。空间复杂度：O(n)，存储 piles 和可能的 prev 数组。 7. 举例验证用 nums = [3, 4, 1, 2, 5] 演示： 3 → [3] 4 → [3, 4] 1 → 替换 3 → [1, 4] 2 → 替换 4 → [1, 2] 5 → 新建 → [1, 2, 5] 堆数为 3，LIS 长度 3，序列为 [3,4,5] 或 [1,2,5] 。注意算法得到的是长度，具体序列取决于追踪方式。 8. 总结 Patience Sorting 在求解 LIS 长度问题上，将时间复杂度从 O(n²) 优化到 O(n log n)，其核心是维护堆顶数组并利用二分查找。该算法也体现了“贪心 + 二分”的思想，是解决 LIS 问题的标准高效算法。