溯源：LIS的O(Nlogn)时间复杂度算法

2022-08-11 约 966 字预计阅读 2 分钟次阅读条评论

周一的时候在LeetCode写每日一题，一道很白的LIS。从以前打比赛开始就基本没怎么写过LIS。工作之后就更没有机会接触这些算法，这次刚好遇到了LIS的题目，想着用O(nlogn)写一下，发现一时半会想不起来是怎么实现的了。折磨了自己一会之后，决定还是好好学一下nlogn的解。由于个人学算法的时候还是更习惯有个具像化的运行逻辑，再根据逻辑记忆代码的实际逻辑，所以对着LIS的nlogn解法一顿猛搜，发现好像大家都只是说出了代码怎么运行，没有说过为什么是这样运行。

因此我一顿Google之后，发现LIS的nlogn解法出处并非是用于解决LIS问题的，而是一种纸牌游戏patience game。

具体的规则如下：

按照顺序将当前的纸牌放入某一个堆中，如果当前牌的大小 x 大于所有牌堆最上方的牌的大小，那么就在最右边新建一个牌堆，将牌放置在新堆上。
如果 x 小于部分牌堆最上方的牌，那么就将 x 放置在所有合法堆中 最左边 的牌堆上。
重复1、2步，直到将所有牌都分堆完成。

这样的放置方法首先保证了：所有堆的堆顶，牌面大小从左到右为递增的。

如下图所示，将[6,4,5,1,8,7,2,3]这8张牌，依照规则放置分堆。最后得到共3个牌堆。

分别为：[1,4,6], [2, 5], [3,7,8]（下标小的为堆底）

想想就会明白，按照这样的规则分堆之后，堆的数量就是这个数组的LIS长度：首先，对于当前数x，如果不存在任意一个堆顶大于x，x将会新建一个堆（堆数+1）对应的，也就是LIS长度+1，如果存在某一个LIS串的一个数 y 大于 x ，那么用 x 来代替 y 在长度为以 y 结尾的LIS串，只会更利于扩张此LIS串的长度，因为 x < y。经过这样的规则分堆，

而第二步的放置方法，就是LIS的logn部分：设dp[i] = 长度为 i 的LIS串中，末尾最小的数。

 if (nums[i] > dp[ans]) dp[++ans] = nums[i];
 else dp[lower_bound(dp, dp + ans + 1, nums[i]) - dp] = nums[i];

这个纸牌游戏除去可以以nlogn复杂度解决LIS问题外，也延伸出了一种新的排序算法：patience sorting，通过上面的规则将纸牌分堆之后，再使用插入排序，完成对无序数组的排序。实际上就是通过分堆数组，来减少插入排序的遍历次数，从而加快插入排序。

每日一题的AC代码：

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int dp[n];
        for(int i = 0; i < n; ++i){
            dp[i] = 0x3f3f3f3f;
        }   
        int ans = 0;
        dp[0] = nums[0];
        for(int i = 1; i < n; ++i){
            if (nums[i] > dp[ans]) dp[++ans] = nums[i];
            else dp[lower_bound(dp, dp + ans + 1, nums[i]) - dp] = nums[i];
        }
        return ans + 1;
    }

目录

溯源：LIS的O(Nlogn)时间复杂度算法