耐心排序并找到最长的递增子序列
Patience sort and finding the longest increasing subsequence
我能够理解找到描述的最长递增子序列的算法 HERE。不过也跟耐心有关sort.As作者说
Bonus: You have learnt Patience Sorting technique partially :).
我曾尝试从其他地方阅读耐心排序，但看不出它与最长递增子序列解决方案有何关系。
我正在尝试进行逆向工程，看看如何从最长递增子序列离开我们的点开始排序。
有人可以就此提出任何建议吗？而且耐心排序的真正目的和优势是什么？
是与堆栈溢出相关的问题，它共享信息，但反过来说——如何使用耐心排序获得最长的递增子序列。
耐心排序只是另一种 O(n lg n) 排序算法（它实际上取决于实现）。如果您以前玩过单人纸牌游戏，那就有点类似了。该算法维护一个堆栈列表，每个堆栈都按降序（从尾到头）排序。数字是递增插入的。
要插入一个数字x，找到最左边栈顶元素大于x 的栈并将x 压入栈中。如果不存在这样的堆栈，则在末尾创建一个新堆栈并将 x 压入其上。请注意，我们插入数字的方式意味着堆栈的顶部元素按递增顺序排序，因此最长递增子序列的长度就是最后的堆数。
一旦所有数字都被插入并准备好堆，我们将反复找到最小数字并将其写入输出。我们从中取出数字的堆栈现在必须插入一个新位置，以便再次对堆栈的顶部元素进行排序。这可以通过使用堆来存储堆栈来完成。
如果您简单地扫描顶部元素以找到最小值并且不使用花哨的数据结构，则该算法采用 O(n sqrt(n)) 这对于小 n 来说还不错。
所以这对数字列表进行排序并为您提供 LIS 的长度（并通过一些扩充为您提供 LIS）。
我能够理解找到描述的最长递增子序列的算法 HERE。不过也跟耐心有关sort.As作者说
Bonus: You have learnt Patience Sorting technique partially :).
我曾尝试从其他地方阅读耐心排序，但看不出它与最长递增子序列解决方案有何关系。 我正在尝试进行逆向工程，看看如何从最长递增子序列离开我们的点开始排序。 有人可以就此提出任何建议吗？而且耐心排序的真正目的和优势是什么？
耐心排序只是另一种 O(n lg n) 排序算法（它实际上取决于实现）。如果您以前玩过单人纸牌游戏，那就有点类似了。该算法维护一个堆栈列表，每个堆栈都按降序（从尾到头）排序。数字是递增插入的。
要插入一个数字x，找到最左边栈顶元素大于x 的栈并将x 压入栈中。如果不存在这样的堆栈，则在末尾创建一个新堆栈并将 x 压入其上。请注意，我们插入数字的方式意味着堆栈的顶部元素按递增顺序排序，因此最长递增子序列的长度就是最后的堆数。
一旦所有数字都被插入并准备好堆，我们将反复找到最小数字并将其写入输出。我们从中取出数字的堆栈现在必须插入一个新位置，以便再次对堆栈的顶部元素进行排序。这可以通过使用堆来存储堆栈来完成。
如果您简单地扫描顶部元素以找到最小值并且不使用花哨的数据结构，则该算法采用 O(n sqrt(n)) 这对于小 n 来说还不错。
所以这对数字列表进行排序并为您提供 LIS 的长度（并通过一些扩充为您提供 LIS）。