Patience Sorting 的最长递增子序列（LIS）应用与证明

这是一个将排序算法与经典组合优化问题结合的精彩题目。Patience Sorting 不仅是一个排序算法，其核心思想还能高效求解最长递增子序列的长度，并重构出任意一个LIS。

题目描述

假设给定一个长度为 n 的整数数组 nums。请实现一种算法，找出这个数组的最长递增子序列的长度，并且返回任意一个这样的子序列。要求时间复杂度优于 O(n²)。

解题过程循序渐进讲解

步骤 1：理解问题
首先，让我们明确什么是“最长递增子序列”。

• 子序列：从原数组中删除一些（0个或多个）元素后，剩下的元素保持原有顺序形成的新序列。
• 递增：子序列中的元素从左到右严格递增（题目中通常可以是非递减，但Patience Sorting逻辑上对应严格递增，我们以严格递增为例）。
• 最长：在所有的递增子序列中，找到包含元素最多的那一个。

例如，对于数组 [10, 9, 2, 5, 3, 7, 101, 18]，其LIS之一是 [2, 3, 7, 101]，长度为4。

暴力搜索所有子序列是指数级的，不可行。经典的动态规划（DP）解法是O(n²)，我们需要更优的O(n log n)方法。这正是Patience Sorting的用武之地。

步骤 2：介绍 Patience Sorting 的基本玩法
Patience Sorting的核心是模拟一个“接龙”游戏，规则如下：

1. 初始化一堆空的“牌堆”。
2. 从左到右遍历数组的每个数字 x。
3. 在现有的所有牌堆中，找到堆顶牌（即每堆最上面的那张牌）大于等于 x 的、最左侧的牌堆。
4. 将 x 作为一张新牌，放入这个牌堆的顶部。
5. 如果找不到这样的牌堆（即所有堆顶牌都小于 x），则新建一个牌堆，将 x 放入。

关键观察：最终牌堆的数量就等于数组的最长递增子序列的长度。这是本算法的核心结论，稍后证明。

步骤 3：用例子演示过程
以数组 [3, 1, 4, 1, 5, 9, 2, 6] 为例，我们来一步一步玩这个游戏。

1. 处理 3： 没有牌堆，新建第1堆: [3]
2. 处理 1： 找堆顶 ≥ 1 的最左牌堆。堆1顶=3 ≥ 1，所以放入堆1: [3, 1]
3. 处理 4： 找堆顶 ≥ 4 的最左牌堆。堆1顶=1 < 4。没有其他牌堆，所以新建第2堆: [4]。牌堆状态：堆1 [3, 1]，堆2 [4]
4. 处理 1： 找堆顶 ≥ 1 的最左牌堆。堆1顶=1 ≥ 1，所以放入堆1: [3, 1, 1]
5. 处理 5： 堆1顶=1 < 5，堆2顶=4 < 5，新建第3堆: [5]。状态：堆1 [3,1,1]，堆2 [4]，堆3 [5]
6. 处理 9： 堆1顶=1 < 9, 堆2顶=4 < 9, 堆3顶=5 < 9，新建第4堆: [9]
7. 处理 2： 找堆顶 ≥ 2 的最左牌堆。堆1顶=1 < 2, 堆2顶=4 ≥ 2, 所以放入堆2: [4, 2]。状态：堆1 [3,1,1], 堆2 [4,2], 堆3 [5], 堆4 [9]
8. 处理 6： 找堆顶 ≥ 6 的最左牌堆。堆1顶=1 < 6, 堆2顶=2 < 6, 堆3顶=5 < 6, 堆4顶=9 ≥ 6, 所以放入堆4: [9, 6]

最终，我们有4个牌堆，所以LIS长度是4。

步骤 4：为什么牌堆数等于LIS长度？——证明
要理解这一点，需要抓住两个不变性：

1. 每个牌堆内部的牌从上到下是递减的（非严格递减）。因为我们在放入一张牌时，总是将其放在堆顶牌大于等于它的最左堆，这意味着新放的牌 x 一定不大于它下面的牌。所以堆内自上而下是：x ≤ 它下面的牌。

2. 在游戏过程中，各牌堆的堆顶牌从左到右是递增的（严格递增）。因为如果有一个新数字 x 需要新建牌堆，说明它比所有已有的堆顶牌都大。如果 x 被放在一个已有的堆上，说明它是找到的第一个堆顶 ≥ x 的堆，那么它左边的堆顶都小于 x，它放上去后成为新的堆顶，仍然大于左边堆顶，而它小于或等于右边的堆顶（如果存在的话）。这个性质可以通过归纳法严格证明。

由于牌堆数等于最终最右边的牌堆编号。对于一个递增子序列，它的元素必须来自不同的牌堆（因为一个牌堆内部是递减的，不能从中取出两个元素构成递增）。因此，LIS长度最多等于牌堆数。

另一方面，我们可以从游戏过程中构造一个长度为“牌堆数”的递增子序列：从最后一个（最右边）牌堆的底部（即该堆的第一张牌）开始，逆着时间线向前回溯。因为每个牌在放入时，其所在堆的左边必然存在一个堆，其当时的堆顶牌小于当前牌（否则就不会新建堆，或者会在更左的堆放置）。通过精心选择（例如，在重建LIS时的标准方法），我们可以保证选出牌堆数那么长的递增序列。因此，LIS长度至少等于牌堆数。

综上，牌堆数严格等于LIS的长度。

步骤 5：算法实现与优化
直接模拟“找最左符合条件的堆顶”操作，如果线性查找，时间复杂度是O(n²)。优化点在于：由于堆顶牌是递增的，我们可以用二分查找来定位应该放入的牌堆。

我们不需要维护整个牌堆的所有牌，只需要维护一个堆顶数组 pile_tops 即可，因为只有堆顶牌用于决定新牌的放置位置。

求解LIS长度（算法核心）

1. 初始化一个空数组 pile_tops，用于存储每个牌堆的堆顶牌。
2. 遍历数组中的每个数 num：
   a. 在 pile_tops 中，使用二分查找（bisect_left）找到第一个大于等于 num 的元素位置 i。
   b. 如果 i 等于 pile_tops 的长度，说明没找到，则 num 比所有堆顶都大，新建牌堆：pile_tops.append(num)。
   c. 否则，说明找到了，用 num 替换 pile_tops[i]。这一步对应着将 num 放入第 i 个牌堆的顶部。
3. 遍历结束后，len(pile_tops) 就是最长递增子序列的长度。

示例代码（Python，求长度）

import bisect
def length_of_lis(nums):
    piles = []  # 存储每个牌堆的堆顶
    for num in nums:
        i = bisect.bisect_left(piles, num)  # 找第一个 >= num 的位置
        if i == len(piles):
            piles.append(num)  # 新建堆
        else:
            piles[i] = num      # 替换堆顶
    return len(piles)

用之前的例子 [3,1,4,1,5,9,2,6] 跑一下：

• piles 变化: [3] -> [1] -> [1,4] -> [1,4] -> [1,4,5] -> [1,4,5,9] -> [1,2,5,9] -> [1,2,5,6]
  最终 piles 长度是4，正确。

步骤 6：如何重构出一个具体的LIS？
pile_tops 数组只存储了最终状态的堆顶，丢失了历史信息。为了重构LIS，我们需要在游戏过程中多记录一些信息。

记录“前一张牌的索引”
我们为原数组的每个元素 nums[i] 记录两个信息：

1. 它被放入的牌堆编号 pile_idx（从0开始计数）。
2. 在同一时刻，它所在牌堆的前一个堆顶（即它被放入时，该堆原来的堆顶）在数组中的索引。如果是新建堆，这个值为-1。

具体步骤修改如下：

1. 除了 pile_tops，我们再维护一个 pile_tops_idx，记录每个牌堆当前堆顶在原数组中的索引。
2. 同时，维护一个 prev 数组，prev[i] 表示在构造LIS时，位于 nums[i] 之前的那个元素在原数组中的索引。
3. 当处理 nums[i] 时：
   a. 用二分查找在 pile_tops 中找到位置 pos。
   b. 计算 prev_idx：如果 pos > 0，则 prev_idx = pile_tops_idx[pos-1]（即前一个牌堆的堆顶索引），否则为 -1。
   c. 如果 pos == len(pile_tops)，新建牌堆：pile_tops.append(num), pile_tops_idx.append(i)。
   d. 否则，替换堆顶：pile_tops[pos] = num, pile_tops_idx[pos] = i。
   e. 记录前驱：prev[i] = prev_idx。
4. 所有元素处理完后，最长递增子序列的长度 L = len(pile_tops)。
5. 要重构LIS，我们从最后一个牌堆的堆顶索引（即 pile_tops_idx[-1]）开始，不断通过 prev 数组向前追溯 L 步，将对应的 nums[index] 加入结果，最后反转即可。

重构示例与代码
对于 nums = [3,1,4,1,5,9,2,6]，模拟重构逻辑（过程略），我们可以得到一个LIS，例如 [1, 4, 5, 6] 或 [1, 2, 5, 6] 等。

import bisect
def lis_with_patience(nums):
    if not nums:
        return [], 0

    piles = []       # 牌堆的当前顶部值
    pile_indices = [] # 牌堆当前顶部值在原数组的索引
    prev = [-1] * len(nums) # 前驱索引

    for i, num in enumerate(nums):
        pos = bisect.bisect_left(piles, num)
        prev_idx = pile_indices[pos-1] if pos > 0 else -1
        if pos == len(piles):
            piles.append(num)
            pile_indices.append(i)
        else:
            piles[pos] = num
            pile_indices[pos] = i
        prev[i] = prev_idx

    # 重构LIS
    lis_length = len(piles)
    lis = []
    cur_idx = pile_indices[-1]  # 最长子序列的最后一个元素索引
    for _ in range(lis_length):
        lis.append(nums[cur_idx])
        cur_idx = prev[cur_idx]
    lis.reverse()
    return lis, lis_length

步骤 7：复杂度分析

• 时间复杂度：O(n log n)。遍历n个元素，每个元素进行一次二分查找 O(log n)。
• 空间复杂度：O(n)。用于存储 prev 数组和 pile_tops, pile_tops_idx 等辅助结构。

这就完成了利用 Patience Sorting 算法高效求解最长递增子序列问题的完整讲解，包括了算法描述、核心原理证明、优化实现和重构方法。