java - 耐心排序并找到最长的递增子序列

Question

我能够理解找到最长递增子序列的算法 HERE .但是也跟耐心排序有关。正如作者所说

Bonus: You have learnt Patience Sorting technique partially :).

我曾尝试从其他地方阅读耐心排序，但看不出它与最长递增子序列解决方案有何关系。我正在尝试进行逆向工程，看看如何从最长递增子序列离开我们的点开始排序。有人可以就此提出任何建议吗？此外，耐心排序的真正目的和优势是什么？

Here是与堆栈溢出相关的问题，它共享信息，但换句话说就是 - 如何使用耐心排序获得最长的递增子序列。

Answer 1

耐心排序只是另一种 O(n lg n) 排序算法(它实际上取决于实现)。如果您以前玩过单人纸牌游戏，那就有点类似了。该算法维护一个堆栈列表，每个堆栈都按降序(从尾到头)排序。数字是递增插入的。

要插入一个数字 x，找到最左边的堆栈，其顶部元素大于 x 并将 x 压入它。如果不存在这样的堆栈，则在末尾创建一个新堆栈并将 x 压入其上。请注意，我们插入数字的方式意味着堆栈的顶部元素按递增顺序排序，因此最长递增子序列的长度就是末尾堆的数量。

一旦所有数字都被插入并且堆就绪，我们将反复找到最小数字并将其写入输出。我们从中取出数字的堆栈现在必须插入一个新位置，以便再次对堆栈的顶部元素进行排序。这可以通过使用堆来存储堆栈来完成。

如果您简单地扫描顶部元素以找到最小值并且不使用花哨的数据结构，则算法采用 O(n sqrt(n)) 这对于小 n 来说还不错。

所以这对数字列表进行排序并为您提供 LIS 的长度(并且通过一些扩充为您提供 LIS)。