leetcode-300 最长上升子序列 O(NlogN)解法

1. 题目内容

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 基本思路

来自极客时间的课程，覃超老师讲的，现在做笔记记录如下：

1. 创建一个数组l用于记录当前的满足要求的最长的子序列；
2. 遍历整个数组，并调整数组l；
3. 调整规则如下：
   <1> 若当前元素大于数组l中所有元素，则l长度加一，将当前元素添加入l
   <2> 否则，找到l中比当前元素大的元素中的最小值，用当前元素替换，使用二分查找（这也是时间复杂度中logN的来源）；
   <3> 遍历完毕后返回l的长度即可

3. 代码实现（Python）

class Solution(object):
    def binary_search(self, num, lts):      # 二分查找，找到当前元素的插入位置
        l = len(lts)
        left = 0
        right = l - 1
        while left < right:
            mid = (left + right) // 2
            if lts[mid] < num < lts[mid+1]:
                return mid+1
            elif num > lts[mid]:
                left = mid+1
            else:
                right = mid

    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        lts = [nums[0]]
        for num in nums[1:]:
            if num > lts[-1]:
                lts.append(num)
            elif num < lts[0]:
                lts[0] = num
            elif num in lts:
                continue
            elif num < lts[-1]:
                n_l = self.binary_search(num, lts)
                lts[n_l] = num
        print(lts)
        return len(lts)


def main():
    nums = [10, 9, 2, 5, 3, 7, 101, 18, 20]
    a = Solution()
    res = a.lengthOfLIS(nums)
    print(res)


if __name__ == '__main__':
    main()

对于main()中给出的数组，遍历时子序列数组内容依次为：

[10]
[9]
[2]
[2, 5]
[2, 3]
[2, 3, 7]
[2, 3, 7, 101]
[2, 3, 7, 18]
[2, 3, 7, 18, 20]

4. 小结

本题较为常规的解法似乎是动态规划，时间复杂度为O(N^2)，本文的解法似乎属于奇技淫巧型，但细想之下会觉得这是需要基础非常牢靠才能想得出的解法，因此记录一下。
此外，这一次顺便复习了二分查找的写法，发现之前掌握的很不牢靠，自己写的很痛苦，想用递归实现，后来去搜了一个例子，才学会，而且更新 left 或 right 的时候需要实际写一下看看要不要 mid±1.