排序算法之：耐心排序（Patience Sorting）的进阶应用——最长递增子序列（LIS）长度求解
字数 3367 2025-11-02 10:11:13

排序算法之：耐心排序（Patience Sorting）的进阶应用——最长递增子序列（LIS）长度求解

题目描述
给定一个整数数组，请使用耐心排序算法的核心思想，设计一个高效的算法来找出该数组中最长递增子序列（Longest Increasing Subsequence, LIS）的长度。例如，对于数组 [10, 9, 2, 5, 3, 7, 101, 18]，最长的递增子序列是 [2, 3, 7, 101] 或 [2, 5, 7, 101]，其长度为4。要求利用耐心排序的“纸牌游戏”规则来求解，并分析其时间复杂度。

解题过程

耐心排序最初是一种基于“分堆”的排序算法，但其核心规则恰好可以用来高效地求解LIS的长度。我们将通过模拟一个纸牌游戏来理解这个过程。

第一步：理解耐心排序的“分堆”规则

想象你有一副随机顺序的扑克牌（对应我们的输入数组）。游戏规则如下：

  1. 你只能查看序列中最上面的一张牌（或者第一张牌）。
  2. 你需要将牌一张一张地翻开。
  3. 对于翻开的每一张新牌：
    a. 你可以选择创建一个新的牌堆，将这张牌作为该牌堆的第一张牌。
    b. 或者，你可以将这张牌放置在某个已有的牌堆上。但是，放置有一个关键规则：新牌的点数必须小于等于该牌堆最上面那张牌的点数。
    c. 一个优化策略是：为了保持牌堆顶部的有序性（便于后续放置），我们总是将新牌放在最左边那个牌堆顶部的牌大于等于新牌的牌堆上。如果所有牌堆顶的牌都小于新牌，则创建一个新牌堆。

这个游戏的目标是使用尽可能少的牌堆。

第二步：将数组模拟为纸牌游戏

让我们用题目中的例子 nums = [10, 9, 2, 5, 3, 7, 101, 18] 来一步步模拟。

  1. 翻看第一张牌 10。目前没有牌堆，因此创建一个新牌堆 Pile 1: [10]。
    牌堆状态: Pile1: [10]

  2. 翻看第二张牌 9。

    • 比较现有牌堆顶：Pile1-top = 10。
    • 9 <= 10，根据规则，我们可以将 9 放在 Pile1 上。根据优化策略，我们选择最左边的可行牌堆（即Pile1）。
    • 放置后，Pile1: [10, 9] (顶部是9)。
      牌堆状态: Pile1: [10, 9]

  3. 翻看第三张牌 2。

    • 比较现有牌堆顶：Pile1-top = 9。
    • 2 <= 9，将 2 放在 Pile1 上。
    • Pile1: [10, 9, 2] (顶部是2)。
      牌堆状态: Pile1: [10, 9, 2]

  4. 翻看第四张牌 5。

    • 比较现有牌堆顶：Pile1-top = 2。
    • 5 > 2，不能放在Pile1上。没有其他牌堆，因此创建一个新牌堆 Pile 2。
    • Pile2: [5]。
      牌堆状态: Pile1: [10, 9, 2], Pile2: [5]

  5. 翻看第五张牌 3。

    • 比较现有牌堆顶：Pile1-top = 2, Pile2-top = 5。
    • 我们需要找到最左边的牌堆顶 >= 3。Pile1-top (2) < 3，不行。Pile2-top (5) >= 3，符合条件。
    • 将 3 放在 Pile2 上。
    • Pile2: [5, 3] (顶部是3)。
      牌堆状态: Pile1: [10, 9, 2], Pile2: [5, 3]

  6. 翻看第六张牌 7。

    • 比较牌堆顶：Pile1-top=2 (<7), Pile2-top=3 (<7)。所有堆顶都小于7。
    • 因此创建一个新牌堆 Pile 3: [7]。
      牌堆状态: Pile1: [10, 9, 2], Pile2: [5, 3], Pile3: [7]

  7. 翻看第七张牌 101。

    • 比较牌堆顶：2, 3, 7 都小于101。
    • 创建新牌堆 Pile 4: [101]。
      牌堆状态: Pile1: [10, 9, 2], Pile2: [5, 3], Pile3: [7], Pile4: [101]

  8. 翻看第八张牌 18。

    • 比较牌堆顶：2, 3, 7, 101。
    • 找到最左边的 >=18 的堆顶。Pile1-top=2 (不行), Pile2-top=3 (不行), Pile3-top=7 (不行), Pile4-top=101 (>=18，符合条件)。
    • 将 18 放在 Pile4 上。
    • Pile4: [101, 18]。
      最终牌堆状态:
      Pile1: [10, 9, 2]
      Pile2: [5, 3]
      Pile3: [7]
      Pile4: [101, 18]

游戏结束。我们最终得到了 4 个牌堆。

第三步：建立牌堆数量与LIS长度的关键联系

一个非常重要的定理（Dilworth定理的推论或Patience Sorting本身的性质）指出：最终形成的牌堆数量，恰好等于原数组最长递增子序列的长度。

在我们的例子中，牌堆数量是4，而LIS的长度也确实为4。你可以这样理解：每个牌堆内部的牌从上到下是递减的（因为后放的牌总是小于等于先放的牌）。而要从不同牌堆中选取牌形成一个递增序列，你最多只能从每个牌堆中选取一张牌（并且必须按照翻牌的顺序，即数组索引顺序）。因此，牌堆的数量限制了你所能形成的递增序列的最大长度。

第四步：算法实现与优化

我们不需要在内存中真正维护每个牌堆的所有牌。我们只关心每个牌堆最上面的那张牌，因为它决定了新牌能否放在这个牌堆上。

我们可以用一个数组 tops 来动态维护所有牌堆的顶部牌。

算法步骤：

  1. 初始化一个空数组 pile_tops。
  2. 遍历输入数组 nums 中的每一个数字 num。
  3. 在 pile_tops 数组中，使用二分查找找到第一个大于等于 num 的元素的位置。
    • 如果找到了这个位置 pos，就用 num 覆盖 pile_tops[pos]。这相当于将 num 放到了那个已有的牌堆上，并更新了该牌堆的顶部牌。
    • 如果没找到（即 num 大于 pile_tops 中的所有元素），则将 num 追加到 pile_tops 的末尾。这相当于创建了一个新的牌堆。
  4. 遍历结束后，pile_tops 数组的长度就是最长递增子序列的长度。

例子 [10, 9, 2, 5, 3, 7, 101, 18] 的算法执行过程：

  1. num=10, pile_tops为空 -> 追加。 pile_tops = [10]
  2. num=9, 在[10]中找第一个>=9的数，是10（位置0）-> 覆盖。 pile_tops = [9]
  3. num=2, 在[9]中找第一个>=2的数，是9（位置0）-> 覆盖。 pile_tops = [2]
  4. num=5, 在[2]中找第一个>=5的数，没找到（5>2）-> 追加。 pile_tops = [2, 5]
  5. num=3, 在[2,5]中找第一个>=3的数，是5（位置1）-> 覆盖。 pile_tops = [2, 3]
  6. num=7, 在[2,3]中找第一个>=7的数，没找到（7>3）-> 追加。 pile_tops = [2, 3, 7]
  7. num=101, 在[2,3,7]中找第一个>=101的数，没找到 -> 追加。 pile_tops = [2, 3, 7, 101]
  8. num=18, 在[2,3,7,101]中找第一个>=18的数，是101（位置3）-> 覆盖。 pile_tops = [2, 3, 7, 18]

最终 pile_tops 的长度为4，即LIS长度。

第五步：复杂度分析

  • 时间复杂度：O(n log n)。我们需要遍历n个元素，对每个元素，在 pile_tops 数组中进行一次二分查找（O(log k)，其中k是当前牌堆数，k <= n）。因此总复杂度是 O(n log n)。
  • 空间复杂度：O(n)。最坏情况下，pile_tops 数组的长度可能为n。

这种方法比动态规划的O(n²)解法更优，是求解最长递增子序列长度的最优算法之一。其核心思想正是源于耐心排序。

排序算法之：耐心排序（Patience Sorting）的进阶应用——最长递增子序列（LIS）长度求解 题目描述 给定一个整数数组，请使用耐心排序算法的核心思想，设计一个高效的算法来找出该数组中最长递增子序列（Longest Increasing Subsequence, LIS）的长度。例如，对于数组 [10, 9, 2, 5, 3, 7, 101, 18] ，最长的递增子序列是 [2, 3, 7, 101] 或 [2, 5, 7, 101] ，其长度为4。要求利用耐心排序的“纸牌游戏”规则来求解，并分析其时间复杂度。 解题过程 耐心排序最初是一种基于“分堆”的排序算法，但其核心规则恰好可以用来高效地求解LIS的长度。我们将通过模拟一个纸牌游戏来理解这个过程。 第一步：理解耐心排序的“分堆”规则 想象你有一副随机顺序的扑克牌（对应我们的输入数组）。游戏规则如下： 你只能查看序列中最上面的一张牌（或者第一张牌）。 你需要将牌一张一张地翻开。 对于翻开的每一张新牌： a. 你可以选择创建一个新的牌堆，将这张牌作为该牌堆的第一张牌。 b. 或者，你可以将这张牌放置在某个 已有的牌堆 上。但是，放置有一个关键规则： 新牌的点数必须小于等于该牌堆最上面那张牌的点数 。 c. 一个优化策略是：为了保持牌堆顶部的有序性（便于后续放置），我们总是将新牌放在 最左边 那个牌堆顶部的牌大于等于新牌的牌堆上。如果所有牌堆顶的牌都小于新牌，则创建一个新牌堆。 这个游戏的目标是使用尽可能少的牌堆。 第二步：将数组模拟为纸牌游戏 让我们用题目中的例子 nums = [10, 9, 2, 5, 3, 7, 101, 18] 来一步步模拟。 翻看第一张牌 10 。目前没有牌堆，因此创建一个新牌堆 Pile 1: [10] 。 牌堆状态: Pile1: [ 10 ] 翻看第二张牌 9 。 比较现有牌堆顶：Pile1-top = 10。 9 <= 10，根据规则，我们可以将 9 放在 Pile1 上。根据优化策略，我们选择最左边的可行牌堆（即Pile1）。 放置后，Pile1: [10, 9] (顶部是9)。 牌堆状态: Pile1: [ 10, 9 ] 翻看第三张牌 2 。 比较现有牌堆顶：Pile1-top = 9。 2 <= 9，将 2 放在 Pile1 上。 Pile1: [10, 9, 2] (顶部是2)。 牌堆状态: Pile1: [ 10, 9, 2 ] 翻看第四张牌 5 。 比较现有牌堆顶：Pile1-top = 2。 5 > 2，不能放在Pile1上。没有其他牌堆，因此创建一个新牌堆 Pile 2。 Pile2: [5] 。 牌堆状态: Pile1: [ 10, 9, 2], Pile2: [ 5 ] 翻看第五张牌 3 。 比较现有牌堆顶：Pile1-top = 2, Pile2-top = 5。 我们需要找到最左边的牌堆顶 >= 3。Pile1-top (2) < 3，不行。Pile2-top (5) >= 3，符合条件。 将 3 放在 Pile2 上。 Pile2: [5, 3] (顶部是3)。 牌堆状态: Pile1: [ 10, 9, 2], Pile2: [ 5, 3 ] 翻看第六张牌 7 。 比较牌堆顶：Pile1-top=2 (<7), Pile2-top=3 ( <7)。所有堆顶都小于7。 因此创建一个新牌堆 Pile 3: [7] 。 牌堆状态: Pile1: [ 10, 9, 2], Pile2: [ 5, 3], Pile3: [ 7 ] 翻看第七张牌 101 。 比较牌堆顶：2, 3, 7 都小于101。 创建新牌堆 Pile 4: [101] 。 牌堆状态: Pile1: [ 10, 9, 2], Pile2: [ 5, 3], Pile3: [ 7], Pile4: [ 101 ] 翻看第八张牌 18 。 比较牌堆顶：2, 3, 7, 101。 找到最左边的 >=18 的堆顶。Pile1-top=2 (不行), Pile2-top=3 (不行), Pile3-top=7 (不行), Pile4-top=101 (>=18，符合条件)。 将 18 放在 Pile4 上。 Pile4: [101, 18] 。 最终牌堆状态: Pile1: [ 10, 9, 2 ] Pile2: [ 5, 3 ] Pile3: [ 7 ] Pile4: [ 101, 18 ] 游戏结束。我们最终得到了 4 个牌堆。 第三步：建立牌堆数量与LIS长度的关键联系 一个非常重要的定理（Dilworth定理的推论或Patience Sorting本身的性质）指出： 最终形成的牌堆数量，恰好等于原数组最长递增子序列的长度。 在我们的例子中，牌堆数量是4，而LIS的长度也确实为4。你可以这样理解：每个牌堆内部的牌从上到下是递减的（因为后放的牌总是小于等于先放的牌）。而要从不同牌堆中选取牌形成一个递增序列，你最多只能从每个牌堆中选取一张牌（并且必须按照翻牌的顺序，即数组索引顺序）。因此，牌堆的数量限制了你所能形成的递增序列的最大长度。 第四步：算法实现与优化 我们不需要在内存中真正维护每个牌堆的所有牌。我们只关心每个牌堆最上面的那张牌，因为它决定了新牌能否放在这个牌堆上。 我们可以用一个数组 tops 来动态维护所有牌堆的顶部牌。 算法步骤： 初始化一个空数组 pile_tops 。 遍历输入数组 nums 中的每一个数字 num 。 在 pile_tops 数组中，使用 二分查找 找到第一个大于等于 num 的元素的位置。 如果找到了这个位置 pos ，就用 num 覆盖 pile_tops[pos] 。这相当于将 num 放到了那个已有的牌堆上，并更新了该牌堆的顶部牌。 如果没找到（即 num 大于 pile_tops 中的所有元素），则将 num 追加到 pile_tops 的末尾。这相当于创建了一个新的牌堆。 遍历结束后， pile_tops 数组的长度就是最长递增子序列的长度。 例子 [10, 9, 2, 5, 3, 7, 101, 18] 的算法执行过程： num=10, pile_tops 为空 -> 追加。 pile_tops = [10] num=9, 在 [10] 中找第一个>=9的数，是10（位置0）-> 覆盖。 pile_tops = [9] num=2, 在 [9] 中找第一个>=2的数，是9（位置0）-> 覆盖。 pile_tops = [2] num=5, 在 [2] 中找第一个>=5的数，没找到（5>2）-> 追加。 pile_tops = [2, 5] num=3, 在 [2,5] 中找第一个>=3的数，是5（位置1）-> 覆盖。 pile_tops = [2, 3] num=7, 在 [2,3] 中找第一个>=7的数，没找到（7>3）-> 追加。 pile_tops = [2, 3, 7] num=101, 在 [2,3,7] 中找第一个>=101的数，没找到 -> 追加。 pile_tops = [2, 3, 7, 101] num=18, 在 [2,3,7,101] 中找第一个>=18的数，是101（位置3）-> 覆盖。 pile_tops = [2, 3, 7, 18] 最终 pile_tops 的长度为4，即LIS长度。 第五步：复杂度分析 时间复杂度：O(n log n)。我们需要遍历n个元素，对每个元素，在 pile_tops 数组中进行一次二分查找（O(log k)，其中k是当前牌堆数，k <= n）。因此总复杂度是 O(n log n)。 空间复杂度：O(n)。最坏情况下， pile_tops 数组的长度可能为n。 这种方法比动态规划的O(n²)解法更优，是求解最长递增子序列长度的最优算法之一。其核心思想正是源于耐心排序。