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

题目描述

给定一个无序的整数数组 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. 理解并实现基于 Patience Sorting 思想的贪心算法来解决 LIS 问题。
2. 解释算法的每一步如何运作，以及它为何是正确的。
3. 分析算法的时间复杂度和空间复杂度。

解题过程循序渐进讲解

1. 问题理解与直观想法

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

但我们可以做得更好。Patience Sorting 是一种纸牌游戏，其核心思想是维护若干个“牌堆”（pile），每个牌堆的顶牌是递增的。这个结构可以巧妙地用来求解 LIS 的长度，并且在过程中可以重构出 LIS 本身。我们今天重点讲解如何用它求长度。

核心洞见：当我们依次处理数组元素时，我们想要构建一个序列，使得序列的每个位置都尽可能存放一个“较小的”数字，这样后面更大的数字才有机会接在后面，从而可能形成更长的递增序列。这本质上是一个贪心策略。

2. 算法核心：维护一个“牌堆顶”数组

我们维护一个数组 piles。piles[i] 表示第 i 个牌堆的顶牌（即当前该堆最上面的那张牌）。这个数组是自动保持递增的。

处理规则：

1. 遍历输入数组 nums 中的每个数字 x。
2. 在 piles 数组中，寻找第一个（最左边的）满足 piles[i] >= x 的牌堆顶索引 i。
   • 如果找到了，就用 x 替换掉 piles[i]。这意味着我们把 x 放到了第 i 个牌堆的顶部。
   • 如果没有找到（即 x 比所有牌堆顶都大），那么我们就在 piles 数组的末尾新建一个牌堆，其顶牌就是 x。这相当于新建了一个牌堆。

3. 逐步模拟

让我们用例子 nums = [10, 9, 2, 5, 3, 7, 101, 18] 来模拟。

• 初始化：piles = []（一个空数组）。
• 处理 10：
  • piles 为空，找不到 piles[i] >= 10。
  • 新建牌堆。piles = [10]。
• 处理 9：
  • 在 piles = [10] 中，寻找第一个 >=9 的元素。piles[0]=10 >= 9，索引 i=0。
  • 用 9 替换 piles[0]。piles = [9]。
  • 解释：9 比 10 小，用 9 替换 10 作为第一个牌堆的顶牌，使得“门槛”变低，未来更容易形成更长的序列。
• 处理 2：
  • 在 piles = [9] 中，piles[0]=9 >= 2，i=0。
  • 替换。piles = [2]。
• 处理 5：
  • 在 piles = [2] 中，piles[0]=2 < 5，不满足 >=5。
  • 找不到，新建牌堆。piles = [2, 5]。
  • 解释：5 比当前所有顶牌都大，它可以接在“以2结尾的递增序列”后面，形成一个新的更长的潜在序列起点（牌堆）。
• 处理 3：
  • 在 piles = [2, 5] 中，寻找第一个 >=3 的。piles[0]=2 < 3，piles[1]=5 >=3，i=1。
  • 用 3 替换 piles[1]。piles = [2, 3]。
  • 解释：3 比 5 小，替换后第二个牌堆的顶牌变小了，这为未来可能接在“第二个位置”的数字提供了更低的门槛。注意，piles 数组 [2, 3] 本身是一个递增序列，但它不一定是原数组的一个子序列！它只是存储了“每个长度下的LIS的最小可能末尾值”。
• 处理 7：
  • 在 piles = [2, 3] 中，piles[0]=2 < 7，piles[1]=3 < 7。
  • 新建牌堆。piles = [2, 3, 7]。
• 处理 101：
  • 在 piles = [2, 3, 7] 中，全部小于101。
  • 新建牌堆。piles = [2, 3, 7, 101]。
• 处理 18：
  • 在 piles = [2, 3, 7, 101] 中，寻找第一个 >=18 的。piles[0], piles[1], piles[2] 都小于18，piles[3]=101 >= 18，i=3。
  • 用 18 替换 piles[3]。piles = [2, 3, 7, 18]。

处理结束。最终 piles 数组的长度为 4，这就是最长递增子序列的长度。

4. 算法正确性解释（为什么长度是对的？）

这个算法巧妙之处在于：

• 性质1：piles 数组始终是严格递增的。因为新建牌堆的条件是当前数字大于所有已有顶牌，而替换操作只会用较小的数字替换一个较大的数字，且替换的位置是第一个不小于它的，这保证了左侧的牌堆顶依然小于它，右侧的大于等于它（但替换后，它可能变得比右侧一些小）。
• 性质2：piles[i] 存储的是所有长度为 i+1 的递增子序列中，可能的最小末尾元素的值。
  • 初始时，长度为1的LIS最小末尾是第一个数。
  • 当我们用二分查找找到第一个 piles[i] >= x 时，意味着 x 可以接在某个以 piles[i-1] 结尾的长度为 i 的递增子序列之后，形成一个长度为 i+1 的递增子序列，并且由于 piles[i] 是旧的、较大的末尾值，我们用更小的 x 去更新它，使得“长度为 i+1 的递增子序列的末尾最小值”变得更优。
  • 如果 x 比所有 piles[i] 都大，说明我们找到了一个更长的递增子序列（长度比当前最长的大1），所以新建一个牌堆。
• 因此，最终牌堆的数量，就等于我们能构建出的最长递增子序列的长度。每个牌堆代表递增子序列中的一个“位置”，而顶牌则是该位置“当前最优”（最小）的候选值。

5. 算法实现与复杂度分析

实现的关键是步骤2中的查找。因为 piles 数组是递增的，我们可以用二分查找。

伪代码：

function lengthOfLIS(nums):
    piles = [] // 存储牌堆顶的数组
    for each x in nums:
        i = binary_search_left(piles, x) // 找到第一个 >= x 的索引
        if i == piles.length:
            piles.append(x) // 新建牌堆
        else:
            piles[i] = x // 替换牌堆顶
    return piles.length

复杂度：

• 时间复杂度：O(n log n)。遍历 n 个元素，对每个元素进行一次 O(log n) 的二分查找。
• 空间复杂度：O(n)。最坏情况下（输入完全递增），piles 数组会增长到长度 n。

6. 扩展：如何重构出 LIS 序列？

仅用 piles 数组无法直接重构序列，因为它只保留了末尾值。为了重构，我们需要在替换操作时，记录每个元素的前驱信息。通常我们会维护一个 parent 数组。在替换 piles[i] 时，parent[x的索引] 记录下 piles[i-1] 对应的原始元素索引（如果 i>0）。最后，从最长序列的末尾（piles 最后一个元素对应的原始元素）开始，根据 parent 链反向追溯即可得到 LIS。重构过程需要 O(n) 额外空间，总时间仍是 O(n log n)。

总结
本题目展示了如何将 Patience Sorting 的贪心思想应用于求解最长递增子序列长度。算法的核心是维护一个代表“各长度LIS最小末尾值”的递增数组，并通过二分查找和替换/追加操作来更新它。这种方法将动态规划的 O(n²) 优化到了 O(n log n)，是解决 LIS 长度问题的经典高效算法。