前言

我们都知道，解决 LIS 的常规解法为 DP，时间复杂度为 O（n^2），但是在一些条件苛刻的问题中，通常 DP 的解法会超时。那么，是否存在一种时间复杂度更优秀的解法呢？答案是肯定的，有一种二分加贪心的解法可以将时间复杂度降低为 O（nlogn）。

详解

如果我们现在要求下面这一组数据的 LIS：

我们需要定义一个数组 g[i] 表示长度为 i 的 LIS 的末尾元素的最小值。接下来，我们依次把 nums[i] 有序地放进 g[i] 里。采用的策略是：

• 如果 nums[i] 比 g[i-1] 大，放进到 g[i] 中；
• 反之，则在 g[] 数组找到第一个比 nums[i] 大的位置替换掉。

过程如下：

此时， g[] 数组填充到第 len 位，LIS 的长度便是 len。不过需要注意的是，此时的 g[] 数组内的值，并不是正确的 LIS。如何理解上面的操作呢？ g[] 长度的突破取决于最后一位数的大小，我们在更新 g[] 数组的时候，贪心的更新了各个长度为 i 的 LIS 的末尾元素的最小值，因此，当遍历完序列时，g[] 数组开辟的长度便是最长递增子序列的长度，这点需要自己好好体会一下。