Patience Sorting 与贪心策略在最长递增子序列问题中的应用

字数 4556 2025-12-08 05:09:11

Patience Sorting 与贪心策略在最长递增子序列问题中的应用

好的，我们来看一个与排序相关，但核心更侧重于动态规划和贪心策略的经典问题：如何利用 Patience Sorting（耐心排序）高效地求解一个序列的最长递增子序列（Longest Increasing Subsequence, LIS）的长度，并最终重构出这个子序列？

这是一个将排序算法思想应用于解决非直接排序问题的绝佳例子。理解它，能让你深刻体会到算法思想之间的美妙联系。

一、问题描述与基础概念

问题：给定一个长度为 n 的整数序列 nums，找出其 最长递增子序列 的长度。如果可以，还需输出该子序列本身。

递增子序列：是原序列的一个子集，元素保持原序，且值严格递增（通常定义为严格递增，但也可为非递减，我们以严格递增为例）。
最长：指的是所有递增子序列中，包含元素最多的那个。

示例：
nums = [10, 9, 2, 5, 3, 7, 101, 18]
最长递增子序列之一是 [2, 3, 7, 101]，长度为 4。

传统方法（动态规划）：
一个经典的动态规划解法是，定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。状态转移方程为：dp[i] = max(dp[j]) + 1，其中 0 <= j < i 且 nums[j] < nums[i]。
时间复杂度为 O(n²)，空间复杂度 O(n)。

我们的目标是找到一个 O(n log n) 时间复杂度的更优解法。

二、解题思路：Patience Sorting 与纸牌游戏

Patience Sorting 源于一个单人纸牌游戏：

有一副牌，我们依次摸牌。
对于每张牌，我们要么：
- 把它放在一个新的牌堆上（如果它比所有现有牌堆的顶牌都大）。
- 要么把它放在最左边的顶牌比它大的那个牌堆上（覆盖之）。
目标是尽可能少地使用牌堆。

关键洞察（Greedy Choice）：

新牌堆：当我们不得不新建一个牌堆时，意味着这张牌是迄今为止遇到的最大值，没有牌堆的顶牌能“容纳”它。这暗示它可能成为一个新潜在递增链的起点。
放在已有牌堆：我们总是放在最左边可放置的牌堆上。这个贪心选择保证了每个牌堆的顶牌是从左到右递增的（因为大的牌会新建或放在右边，小的牌会覆盖左边的某个顶牌）。

这个过程与寻找 LIS 有何关系？牌堆的数量，就等于最长递增子序列的长度！

三、循序渐进的计算过程

我们使用一个数组 pile_tops 来动态维护所有牌堆的顶牌。

步骤一：仅计算长度

让我们以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例。

初始：pile_tops = []。
处理 10：pile_tops 为空，新建牌堆。
pile_tops = [10]。
处理 9：在 pile_tops 中寻找第一个 >= 9 的顶牌，是 pile_tops[0]=10。用 9 覆盖它。
pile_tops = [9]。
解读：9比10小，它开启了一个更“有潜力”增长的新序列头部。
处理 2：寻找第一个 >= 2 的顶牌，是 pile_tops[0]=9。覆盖。
pile_tops = [2]。
处理 5：寻找第一个 >= 5 的顶牌，没有找到（2 < 5），所以新建牌堆。
pile_tops = [2, 5]。
解读：5不能放在2上（因为2<5，但规则是覆盖第一个比自己大的），所以它新建了一个序列。现在我们有2->5这个潜在序列。
处理 3：寻找第一个 >= 3 的顶牌，是 pile_tops[1]=5。覆盖。
pile_tops = [2, 3]。
解读：3比5小，放在5的位置上，意味着以3结尾的序列比以5结尾的（在当前看来）更有潜力接上更小的后续牌。
处理 7：寻找第一个 >= 7 的顶牌，没有找到（3 < 7），新建牌堆。
pile_tops = [2, 3, 7]。
处理 101：寻找第一个 >= 101 的顶牌，没有找到，新建牌堆。
pile_tops = [2, 3, 7, 101]。
处理 18：寻找第一个 >= 18 的顶牌，是 pile_tops[3]=101。覆盖。
pile_tops = [2, 3, 7, 18]。

过程结束。pile_tops 的长度为 4，即 LIS 的长度为 4。

算法实现细节：
寻找 “第一个 >= x 的顶牌” 这一步，因为 pile_tops 总是保持有序，我们可以使用二分查找（Binary Search）。

def length_of_lis(nums):
    pile_tops = []
    for num in nums:
        # 二分查找：在pile_tops中找第一个 >= num 的索引
        left, right = 0, len(pile_tops)
        while left < right:
            mid = left + (right - left) // 2
            if pile_tops[mid] < num:
                left = mid + 1
            else: # pile_tops[mid] >= num
                right = mid
        # left 是应该放置或覆盖的位置
        if left == len(pile_tops):
            pile_tops.append(num) # 新建牌堆
        else:
            pile_tops[left] = num # 覆盖现有顶牌
    return len(pile_tops)

时间复杂度：O(n log n)。空间复杂度：O(n)。

四、进阶：如何重构出具体的 LIS？

仅仅知道长度往往不够，我们需要知道这个子序列具体是什么。pile_tops 最终存储的 [2, 3, 7, 18] 并不一定是真正的 LIS（在这个例子里凑巧是 [2,3,7,101]）。

重构的关键：在处理每一张牌（数字）时，我们需要记录它被放在哪个牌堆上（堆索引，从0开始）。

堆索引的意义：以 num 结尾的、当前可能的最长递增子序列的长度，正好是 (堆索引 + 1)。
链接信息：为了能回溯出序列，对于每个数字，我们还需要记录它所在牌堆的前一张牌（即“压”在它下面的牌）在原数组中的索引。但更简单的方法是：在覆盖一个顶牌时，被覆盖的顶牌就自然地成为了新牌的“前驱”。

重构算法步骤：

维护两个数组：
- pile_tops: 存储每个牌堆当前的顶牌在原数组中的索引（不再是值）。
- prev_pointer: 长度等于 n，prev_pointer[i] 表示在由 nums[i] 构成的潜在序列中，nums[i] 的前一个元素在原数组中的索引。如果 nums[i] 是某个序列的第一个元素，则 prev_pointer[i] = -1。
遍历每个数字 nums[i]：
- 用二分查找在 pile_tops (根据其存储的索引对应的值) 中找第一个 >= nums[i] 的位置 pile_idx。
- 确定 nums[i] 的前驱：
  - 如果 pile_idx == 0，nums[i] 是新的最小序列头，prev_pointer[i] = -1。
  - 否则，它的前驱就是 pile_tops[pile_idx - 1] 这个索引对应的值。
- 更新 pile_tops[pile_idx] = i。
遍历结束后，pile_tops 的最后一个元素索引 last_idx，就是某个最长递增子序列最后一个元素的位置。
根据 prev_pointer 从 last_idx 开始向前回溯，即可得到逆序的 LIS，最后反转。

以示例演示重构过程 (nums = [10, 9, 2, 5, 3, 7, 101, 18])：

i	num	pile_tops (存储索引)	prev_pointer	解释
0	10	[0]	[-1, ?, ?, ?, ?, ?, ?, ?]	新建堆0，无前驱。
1	9	[1]	[-1, -1, ?, ?, ?, ?, ?, ?]	覆盖堆0，9是堆0新头，无前驱。
2	2	[2]	[-1, -1, -1, ?, ?, ?, ?, ?]	覆盖堆0，2是新头。
3	5	[2, 3]	[-1, -1, -1, 2, ?, ?, ?, ?]	新建堆1，放在堆0(索引2)后面，所以前驱是索引2(值2)。
4	3	[2, 4]	[-1, -1, -1, 2, 2, ?, ?, ?]	覆盖堆1，前驱是堆0的顶(索引2)。
5	7	[2, 4, 5]	[-1, -1, -1, 2, 2, 4, ?, ?]	新建堆2，前驱是堆1的顶(索引4，值3)。
6	101	[2, 4, 5, 6]	[-1,-1,-1,2,2,4,5,?]	新建堆3，前驱是堆2的顶(索引5，值7)。
7	18	[2, 4, 5, 7]	[-1,-1,-1,2,2,4,5,5]	覆盖堆3，前驱是堆2的顶(索引5，值7)。

过程结束。

pile_tops 最后是 [2, 4, 5, 7]，长度为4。
最后一个元素索引是 7 (值18)。
回溯 prev_pointer: prev[7]=5 -> prev[5]=4 -> prev[4]=2 -> prev[2]=-1 停止。
得到的索引链逆序为: [7, 5, 4, 2]，对应值为 [18, 7, 3, 2]。
注意：这得到的 [2, 3, 7, 18] 是一个有效的最长递增子序列，但并非题目最初示例的 [2, 3, 7, 101]。因为 Patience Sorting 找到的是所有可能 LIS 中，根据其贪心规则（最小化顶牌）所确定的那一个。它依然是正确的 LIS。

五、算法总结与理解要点

核心思想：将寻找 LIS 转化为一个维护有序序列（牌堆顶）的过程，利用贪心策略（总是放在最左边的可行位置）来保证正确性。
为什么牌堆数 = LIS 长度？
- 每个牌堆的牌从上到下形成一个递减序列（因为后放的牌更小）。
- 从不同牌堆各取一张牌（比如都取最底下的，或都取顶牌），不能保证是递增的。
- 关键的证明在于：对于任意时刻，如果有 k 个牌堆，那么必然存在一个长度为 k 的递增子序列（可以从每个牌堆取一张特定的牌，例如每堆取历史上成为该堆第一张牌的那张牌，它们形成递增关系）。同时，不可能存在长度超过 k 的递增子序列（否则根据鸽巢原理，这个长序列的某两张牌会出现在同一个递减的牌堆里，矛盾）。因此，k 就是当前已处理部分的 LIS 长度。
时间与空间：
- 时间复杂度：O(n log n)，主要开销在 n 次二分查找。
- 空间复杂度：O(n)，用于存储牌堆顶和回溯信息。
与动态规划的关系：可以认为 pile_tops 数组是在维护动态规划中“长度为 i 的递增子序列的最小可能结尾值”。这比朴素的 O(n²) DP 更高效。

通过这个例子，你不仅学会了一个高效的 LIS 算法，更重要的是理解了 Patience Sorting 这一思想如何巧妙地应用于解决一个经典的组合优化问题，展现了算法设计中“转化”与“贪心”的威力。

Patience Sorting 与贪心策略在最长递增子序列问题中的应用好的，我们来看一个与排序相关，但核心更侧重于动态规划和贪心策略的经典问题：如何利用 Patience Sorting（耐心排序）高效地求解一个序列的最长递增子序列（Longest Increasing Subsequence, LIS）的长度，并最终重构出这个子序列？这是一个将排序算法思想应用于解决非直接排序问题的绝佳例子。理解它，能让你深刻体会到算法思想之间的美妙联系。一、问题描述与基础概念问题：给定一个长度为 n 的整数序列 nums ，找出其最长递增子序列的长度。如果可以，还需输出该子序列本身。递增子序列：是原序列的一个子集，元素保持原序，且值严格递增（通常定义为严格递增，但也可为非递减，我们以严格递增为例）。最长：指的是所有递增子序列中，包含元素最多的那个。示例： nums = [10, 9, 2, 5, 3, 7, 101, 18] 最长递增子序列之一是 [2, 3, 7, 101] ，长度为 4。传统方法（动态规划）：一个经典的动态规划解法是，定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。状态转移方程为： dp[i] = max(dp[j]) + 1 ，其中 0 <= j < i 且 nums[j] < nums[i] 。时间复杂度为 O(n²)，空间复杂度 O(n)。我们的目标是找到一个 O(n log n) 时间复杂度的更优解法。二、解题思路：Patience Sorting 与纸牌游戏 Patience Sorting 源于一个单人纸牌游戏：有一副牌，我们依次摸牌。对于每张牌，我们要么：把它放在一个新的牌堆上（如果它比所有现有牌堆的顶牌都大）。要么把它放在最左边的顶牌比它大的那个牌堆上（覆盖之）。目标是尽可能少地使用牌堆。关键洞察（Greedy Choice）：新牌堆：当我们不得不新建一个牌堆时，意味着这张牌是迄今为止遇到的最大值，没有牌堆的顶牌能“容纳”它。这暗示它可能成为一个新潜在递增链的起点。放在已有牌堆：我们总是放在最左边可放置的牌堆上。这个贪心选择保证了每个牌堆的顶牌是从左到右递增的（因为大的牌会新建或放在右边，小的牌会覆盖左边的某个顶牌）。这个过程与寻找 LIS 有何关系？牌堆的数量，就等于最长递增子序列的长度！三、循序渐进的计算过程我们使用一个数组 pile_tops 来动态维护所有牌堆的顶牌。步骤一：仅计算长度让我们以 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例。初始： pile_tops = [] 。处理 10 ： pile_tops 为空，新建牌堆。 pile_tops = [10] 。处理 9 ：在 pile_tops 中寻找第一个 >= 9 的顶牌，是 pile_tops[0]=10 。用 9 覆盖它。 pile_tops = [9] 。解读：9比10小，它开启了一个更“有潜力”增长的新序列头部。处理 2 ：寻找第一个 >= 2 的顶牌，是 pile_tops[0]=9 。覆盖。 pile_tops = [2] 。处理 5 ：寻找第一个 >= 5 的顶牌，没有找到（2 < 5），所以新建牌堆。 pile_tops = [2, 5] 。解读：5不能放在2上（因为2<5，但规则是覆盖第一个比自己大的），所以它新建了一个序列。现在我们有2->5这个潜在序列。处理 3 ：寻找第一个 >= 3 的顶牌，是 pile_tops[1]=5 。覆盖。 pile_tops = [2, 3] 。解读：3比5小，放在5的位置上，意味着以3结尾的序列比以5结尾的（在当前看来）更有潜力接上更小的后续牌。处理 7 ：寻找第一个 >= 7 的顶牌，没有找到（3 < 7），新建牌堆。 pile_tops = [2, 3, 7] 。处理 101 ：寻找第一个 >= 101 的顶牌，没有找到，新建牌堆。 pile_tops = [2, 3, 7, 101] 。处理 18 ：寻找第一个 >= 18 的顶牌，是 pile_tops[3]=101 。覆盖。 pile_tops = [2, 3, 7, 18] 。过程结束。 pile_tops 的长度为 4 ，即 LIS 的长度为 4。算法实现细节：寻找 “第一个 >= x 的顶牌” 这一步，因为 pile_tops 总是保持有序，我们可以使用二分查找（Binary Search）。时间复杂度：O(n log n)。空间复杂度：O(n)。四、进阶：如何重构出具体的 LIS？仅仅知道长度往往不够，我们需要知道这个子序列具体是什么。 pile_tops 最终存储的 [2, 3, 7, 18] 并不一定是真正的 LIS（在这个例子里凑巧是 [2,3,7,101] ）。重构的关键：在处理每一张牌（数字）时，我们需要记录它被放在哪个牌堆上（堆索引，从0开始）。堆索引的意义：以 num 结尾的、当前可能的最长递增子序列的长度，正好是 (堆索引 + 1) 。链接信息：为了能回溯出序列，对于每个数字，我们还需要记录它所在牌堆的前一张牌（即“压”在它下面的牌）在原数组中的索引。但更简单的方法是：在覆盖一个顶牌时，被覆盖的顶牌就自然地成为了新牌的“前驱”。重构算法步骤：维护两个数组： pile_tops : 存储每个牌堆当前的顶牌在原数组中的索引（不再是值）。 prev_pointer : 长度等于 n ， prev_pointer[i] 表示在由 nums[i] 构成的潜在序列中， nums[i] 的前一个元素在原数组中的索引。如果 nums[i] 是某个序列的第一个元素，则 prev_pointer[i] = -1 。遍历每个数字 nums[i] ：用二分查找在 pile_tops (根据其存储的索引对应的值) 中找第一个 >= nums[i] 的位置 pile_idx 。确定 nums[i] 的前驱：如果 pile_idx == 0 ， nums[i] 是新的最小序列头， prev_pointer[i] = -1 。否则，它的前驱就是 pile_tops[pile_idx - 1] 这个索引对应的值。更新 pile_tops[pile_idx] = i 。遍历结束后， pile_tops 的最后一个元素索引 last_idx ，就是某个最长递增子序列最后一个元素的位置。根据 prev_pointer 从 last_idx 开始向前回溯，即可得到逆序的 LIS，最后反转。以示例演示重构过程 ( nums = [10, 9, 2, 5, 3, 7, 101, 18] )： | i | num | pile_ tops (存储索引) | prev_ pointer | 解释 | |---|-----|---------------------|--------------|------| |0 | 10 | [ 0] | [ -1, ?, ?, ?, ?, ?, ?, ? ] | 新建堆0，无前驱。| |1 | 9 | [ 1] | [ -1, -1, ?, ?, ?, ?, ?, ? ] | 覆盖堆0，9是堆0新头，无前驱。| |2 | 2 | [ 2] | [ -1, -1, -1, ?, ?, ?, ?, ? ] | 覆盖堆0，2是新头。| |3 | 5 | [ 2, 3] | [ -1, -1, -1, 2, ?, ?, ?, ? ] | 新建堆1，放在堆0(索引2)后面，所以前驱是索引2(值2)。| |4 | 3 | [ 2, 4] | [ -1, -1, -1, 2, 2, ?, ?, ? ] | 覆盖堆1，前驱是堆0的顶(索引2)。| |5 | 7 | [ 2, 4, 5] | [ -1, -1, -1, 2, 2, 4, ?, ? ] | 新建堆2，前驱是堆1的顶(索引4，值3)。| |6 |101| [ 2, 4, 5, 6] | [ -1,-1,-1,2,2,4,5,? ] | 新建堆3，前驱是堆2的顶(索引5，值7)。| |7 |18 | [ 2, 4, 5, 7] | [ -1,-1,-1,2,2,4,5,5 ] | 覆盖堆3，前驱是堆2的顶(索引5，值7)。| 过程结束。 pile_tops 最后是 [2, 4, 5, 7] ，长度为4。最后一个元素索引是 7 (值18)。回溯 prev_pointer : prev[7]=5 -> prev[5]=4 -> prev[4]=2 -> prev[2]=-1 停止。得到的索引链逆序为: [7, 5, 4, 2] ，对应值为 [18, 7, 3, 2] 。注意：这得到的 [2, 3, 7, 18] 是一个有效的最长递增子序列，但并非题目最初示例的 [2, 3, 7, 101] 。因为 Patience Sorting 找到的是所有可能 LIS 中，根据其贪心规则（最小化顶牌）所确定的那一个。它依然是正确的 LIS。五、算法总结与理解要点核心思想：将寻找 LIS 转化为一个维护有序序列（牌堆顶）的过程，利用贪心策略（总是放在最左边的可行位置）来保证正确性。为什么牌堆数 = LIS 长度？每个牌堆的牌从上到下形成一个递减序列（因为后放的牌更小）。从不同牌堆各取一张牌（比如都取最底下的，或都取顶牌），不能保证是递增的。关键的证明在于：对于任意时刻，如果有 k 个牌堆，那么必然存在一个长度为 k 的递增子序列（可以从每个牌堆取一张特定的牌，例如每堆取历史上成为该堆第一张牌的那张牌，它们形成递增关系）。同时，不可能存在长度超过 k 的递增子序列（否则根据鸽巢原理，这个长序列的某两张牌会出现在同一个递减的牌堆里，矛盾）。因此， k 就是当前已处理部分的 LIS 长度。时间与空间：时间复杂度：O(n log n)，主要开销在 n 次二分查找。空间复杂度：O(n)，用于存储牌堆顶和回溯信息。与动态规划的关系：可以认为 pile_tops 数组是在维护动态规划中“长度为 i 的递增子序列的最小可能结尾值”。这比朴素的 O(n²) DP 更高效。通过这个例子，你不仅学会了一个高效的 LIS 算法，更重要的是理解了 Patience Sorting 这一思想如何巧妙地应用于解决一个经典的组合优化问题，展现了算法设计中“转化”与“贪心”的威力。

一、 问题描述与基础概念

二、 解题思路：Patience Sorting 与纸牌游戏

三、 循序渐进的计算过程