耐心排序

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

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

int lengthOfLIS(int[] nums) {
    int[] top = new int[nums.length];
    // 牌堆数初始化为 0
    int piles = 0;
    for (int i = 0; i < nums.length; i++) {
    // 要处理的扑克牌
    int poker = nums[i];

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

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