排序算法之：Patience Sorting（耐心排序）的动态规划与最长递增子序列长度求解优化
字数 2277 2025-12-07 10:33:48

排序算法之：Patience Sorting（耐心排序）的动态规划与最长递增子序列长度求解优化

题目描述
耐心排序（Patience Sorting）是一种基于比较的排序算法，其核心思想是将待排序元素依次放入一系列“堆叠”（pile）中，并利用这些堆叠的有序性最终完成排序。这个算法有一个非常著名的衍生应用：无需显式排序，就能高效地计算出序列的最长递增子序列（Longest Increasing Subsequence, LIS）的长度。

题目要求：
给定一个无序的整数数组 nums，请你使用耐心排序的核心思想，设计一个算法，在 O(n log n) 的时间复杂度内找出该数组的最长递增子序列的长度。
注意：你不需要输出具体的 LIS，只需返回其长度。

解题过程循序渐进讲解

耐心排序的“堆叠”规则是理解本题的关键。我们先从排序的原始操作开始，逐步过渡到 LIS 长度的求解优化。

步骤1：理解耐心排序的“堆叠”规则
想象你有一副扑克牌，需要按点数从小到大排序。耐心排序的摆牌规则如下：

  1. 依次遍历每一张牌（数组的每个元素）。
  2. 对于当前牌 x，查看已有堆叠的顶牌（每个堆叠最上面的牌）：
    • 如果存在顶牌数值 ≥ x 的堆叠，则选择其中顶牌最小的那个堆叠，将 x 放在其顶部。
    • 如果所有堆叠的顶牌都 < x，则为 x 新建一个堆叠。
  3. 重复直至所有牌处理完毕。

这个规则保证了：

  • 每个堆叠内部的牌从顶到底是递减的（因为顶牌≥新牌，所以新牌更小或相等）。
  • 不同堆叠的顶牌从左到右是递增的（因为新建堆叠意味着当前牌比所有已有顶牌都大）。

示例：nums = [3, 5, 1, 2, 6, 4]

  • 牌3：无堆叠 → 新建堆叠1: [3]
  • 牌5：顶牌3<5 → 新建堆叠2: [5]
  • 牌1：顶牌3≥1，选最小顶牌堆叠1 → 堆叠1: [3, 1]
  • 牌2：顶牌1<2，顶牌5≥2 → 选最小顶牌5的堆叠2 → 堆叠2: [5, 2]
  • 牌6：顶牌1<6，顶牌2<6 → 新建堆叠3: [6]
  • 牌4：顶牌1<4，顶牌2<4，顶牌6≥4 → 选最小顶牌6的堆叠3 → 堆叠3: [6, 4]

最终堆叠：

堆1: 顶1 (底3)  
堆2: 顶2 (底5)  
堆3: 顶4 (底6)

步骤2：从排序到 LIS 长度的关键观察
一个重要定理（由 Aldous 和 Diaconis 提出）：堆叠的数量等于最长递增子序列的长度。

直观理解：

  • 每个堆叠相当于一个“链”，链中元素是递减的。
  • 要形成一个递增子序列，我们必须从不同的堆叠中各取一个元素（且顺序必须是从左到右的堆叠，因为顶牌递增）。
  • 堆叠数量限制了递增子序列的最大长度，且我们可以构造出一个长度等于堆叠数的递增子序列（例如，取每个堆叠的底牌，在示例中为3,5,6，这是一个递增子序列）。

因此，我们无需真正维护堆叠内容，只需维护每个堆叠的顶牌值，并统计最终堆叠数。

步骤3：优化实现——使用数组与二分查找
我们维护一个数组 tops，tops[i] 表示第 i 个堆叠的顶牌值（最小的索引对应最左边的堆叠）。
遍历每个数字 x：

  1. 在 tops 中寻找第一个 ≥ x 的位置（二分查找）。
  2. 如果找到，用 x 替换该位置的顶牌（相当于放到对应堆叠顶）。
  3. 如果没找到（x 大于所有顶牌），则在 tops 末尾追加 x（新建堆叠）。

遍历完成后，tops 的长度就是堆叠数，即 LIS 长度。

为什么可行：

  • tops 数组始终保持递增（因为替换操作不会破坏有序性，且追加时 x 一定最大）。
  • 查找第一个 ≥ x 的位置等同于“选择最小顶牌且 ≥ x 的堆叠”。

步骤4：示例演算
nums = [3, 5, 1, 2, 6, 4]

  1. x=3: tops=[] → 追加 → tops=[3]
  2. x=5: 查找≥5 → 无 → 追加 → tops=[3,5]
  3. x=1: 查找≥1 → 位置0(值3) → 替换 → tops=[1,5]
  4. x=2: 查找≥2 → 位置1(值5) → 替换 → tops=[1,2]
  5. x=6: 查找≥6 → 无 → 追加 → tops=[1,2,6]
  6. x=4: 查找≥4 → 位置2(值6) → 替换 → tops=[1,2,4]

最终 tops 长度=3，即 LIS 长度为3。验证：LIS 可以是 [1,2,6] 或 [1,2,4] 等。

步骤5：算法复杂度分析

  • 遍历 n 个元素，每次在 tops 上进行二分查找（O(log L)，L≤n），总时间复杂度为 O(n log n)。
  • 空间复杂度 O(n)，用于 tops 数组。

步骤6：边界与注意事项

  • 如果数组允许重复值，根据 LIS 的严格递增定义（通常要求递增，即后>前），查找时应使用“第一个 ≥ x”而不是“> x”，这样可以保证相等数字不会出现在同一递增子序列中（替换操作会将相等数字放在不同位置，但不会增加堆叠数，符合 LIS 计数规则）。
  • 此方法只返回长度，若需输出具体 LIS，需额外记录信息（如前驱指针），但题目不要求。

总结
耐心排序的堆叠思想巧妙地将最长递增子序列问题转化为一个维护有序顶牌数组的过程。通过二分查找优化，我们可以在 O(n log n) 时间内高效得到 LIS 长度，这比动态规划 O(n²) 的方法更优。此算法在计算序列的“递增潜力”时非常高效，是算法设计中“数据结构优化动态规划”的经典案例。

排序算法之：Patience Sorting（耐心排序）的动态规划与最长递增子序列长度求解优化 题目描述 耐心排序（Patience Sorting）是一种基于比较的排序算法，其核心思想是将待排序元素依次放入一系列“堆叠”（pile）中，并利用这些堆叠的有序性最终完成排序。这个算法有一个非常著名的衍生应用： 无需显式排序，就能高效地计算出序列的最长递增子序列（Longest Increasing Subsequence, LIS）的长度 。 题目要求： 给定一个无序的整数数组 nums ，请你使用耐心排序的核心思想，设计一个算法，在 O(n log n) 的时间复杂度内找出该数组的最长递增子序列的长度。 注意：你不需要输出具体的 LIS，只需返回其长度。 解题过程循序渐进讲解 耐心排序的“堆叠”规则是理解本题的关键。我们先从排序的原始操作开始，逐步过渡到 LIS 长度的求解优化。 步骤1：理解耐心排序的“堆叠”规则 想象你有一副扑克牌，需要按点数从小到大排序。耐心排序的摆牌规则如下： 依次遍历每一张牌（数组的每个元素）。 对于当前牌 x ，查看已有堆叠的 顶牌 （每个堆叠最上面的牌）： 如果存在顶牌数值 ≥ x 的堆叠，则选择其中 顶牌最小的那个堆叠 ，将 x 放在其顶部。 如果所有堆叠的顶牌都 < x ，则为 x 新建一个堆叠。 重复直至所有牌处理完毕。 这个规则保证了： 每个堆叠内部的牌从顶到底是递减的（因为顶牌≥新牌，所以新牌更小或相等）。 不同堆叠的顶牌从左到右是递增的（因为新建堆叠意味着当前牌比所有已有顶牌都大）。 示例 ： nums = [3, 5, 1, 2, 6, 4] 牌3：无堆叠 → 新建堆叠1: [ 3 ] 牌5：顶牌3<5 → 新建堆叠2: [ 5 ] 牌1：顶牌3≥1，选最小顶牌堆叠1 → 堆叠1: [ 3, 1 ] 牌2：顶牌1<2，顶牌5≥2 → 选最小顶牌5的堆叠2 → 堆叠2: [ 5, 2 ] 牌6：顶牌1<6，顶牌2<6 → 新建堆叠3: [ 6 ] 牌4：顶牌1<4，顶牌2<4，顶牌6≥4 → 选最小顶牌6的堆叠3 → 堆叠3: [ 6, 4 ] 最终堆叠： 步骤2：从排序到 LIS 长度的关键观察 一个重要定理（由 Aldous 和 Diaconis 提出）： 堆叠的数量等于最长递增子序列的长度 。 直观理解： 每个堆叠相当于一个“链”，链中元素是递减的。 要形成一个递增子序列，我们必须从不同的堆叠中各取一个元素（且顺序必须是从左到右的堆叠，因为顶牌递增）。 堆叠数量限制了递增子序列的最大长度，且我们可以构造出一个长度等于堆叠数的递增子序列（例如，取每个堆叠的底牌，在示例中为3,5,6，这是一个递增子序列）。 因此， 我们无需真正维护堆叠内容，只需维护每个堆叠的顶牌值，并统计最终堆叠数 。 步骤3：优化实现——使用数组与二分查找 我们维护一个数组 tops ， tops[i] 表示第 i 个堆叠的顶牌值（最小的索引对应最左边的堆叠）。 遍历每个数字 x ： 在 tops 中寻找第一个 ≥ x 的位置（二分查找）。 如果找到，用 x 替换该位置的顶牌（相当于放到对应堆叠顶）。 如果没找到（ x 大于所有顶牌），则在 tops 末尾追加 x （新建堆叠）。 遍历完成后， tops 的长度就是堆叠数，即 LIS 长度。 为什么可行 ： tops 数组始终保持递增（因为替换操作不会破坏有序性，且追加时 x 一定最大）。 查找第一个 ≥ x 的位置等同于“选择最小顶牌且 ≥ x 的堆叠”。 步骤4：示例演算 nums = [3, 5, 1, 2, 6, 4] x=3: tops=[] → 追加 → tops=[ 3 ] x=5: 查找≥5 → 无 → 追加 → tops=[ 3,5 ] x=1: 查找≥1 → 位置0(值3) → 替换 → tops=[ 1,5 ] x=2: 查找≥2 → 位置1(值5) → 替换 → tops=[ 1,2 ] x=6: 查找≥6 → 无 → 追加 → tops=[ 1,2,6 ] x=4: 查找≥4 → 位置2(值6) → 替换 → tops=[ 1,2,4 ] 最终 tops 长度=3，即 LIS 长度为3。验证：LIS 可以是 [ 1,2,6] 或 [ 1,2,4 ] 等。 步骤5：算法复杂度分析 遍历 n 个元素，每次在 tops 上进行二分查找（O(log L)，L≤n），总时间复杂度为 O(n log n)。 空间复杂度 O(n)，用于 tops 数组。 步骤6：边界与注意事项 如果数组允许重复值，根据 LIS 的 严格递增 定义（通常要求递增，即后>前），查找时应使用“第一个 ≥ x”而不是“> x”，这样可以保证相等数字不会出现在同一递增子序列中（替换操作会将相等数字放在不同位置，但不会增加堆叠数，符合 LIS 计数规则）。 此方法只返回长度，若需输出具体 LIS，需额外记录信息（如前驱指针），但题目不要求。 总结 耐心排序的堆叠思想巧妙地将最长递增子序列问题转化为一个维护有序顶牌数组的过程。通过二分查找优化，我们可以在 O(n log n) 时间内高效得到 LIS 长度，这比动态规划 O(n²) 的方法更优。此算法在计算序列的“递增潜力”时非常高效，是算法设计中“数据结构优化动态规划”的经典案例。