耐心排序

来自维基百科：耐心排序是计算机科学中的一种排序算法，它使用纸牌游戏”耐心”的规则按值对元素列表进行排序。游戏的目标是形成尽可能少的牌堆。耐心排序可用于解决最长递增序列（LIS）问题。

我们可以跳过证明，详细证明请参考文档。我们只需要知道牌堆数等于最长递增序列的长度。

def length_of_lis(nums):
    top = [0] * len(nums)
    # 牌堆数初始化为 0
    piles = 0
    for i in range(len(nums)):
        # 要处理的扑克牌
        poker = nums[i]

        # ***** 搜索左侧边界的二分查找 *****
        left, right = 0, piles
        while left < right:
            mid = (left + right) // 2
            if top[mid] > poker:
                right = mid
            elif top[mid] < poker:
                left = mid + 1
            else:
                right = mid

        # 没找到合适的牌堆，新建一堆
        if left == piles:
            piles += 1
        # 把这张牌放到牌堆顶
        top[left] = poker
    # 牌堆数就是 LIS 长度
    return piles