本文主要是介绍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. 基本思路
来自极客时间的课程，覃超老师讲的，现在做笔记记录如下：
- 创建一个数组
l用于记录当前的满足要求的最长的子序列；- 遍历整个数组，并调整数组
l；- 调整规则如下：
<1> 若当前元素大于数组l中所有元素，则l长度加一，将当前元素添加入l
<2> 否则，找到l中比当前元素大的元素中的最小值，用当前元素替换，使用二分查找（这也是时间复杂度中logN的来源）；
<3> 遍历完毕后返回l的长度即可
3. 代码实现（Python）
class Solution(object):def binary_search(self, num, lts): # 二分查找，找到当前元素的插入位置l = len(lts)left = 0right = l - 1while left < right:mid = (left + right) // 2if lts[mid] < num < lts[mid+1]:return mid+1elif num > lts[mid]:left = mid+1else:right = middef lengthOfLIS(self, nums):""":type nums: List[int]:rtype: int"""if not nums:return 0lts = [nums[0]]for num in nums[1:]:if num > lts[-1]:lts.append(num)elif num < lts[0]:lts[0] = numelif num in lts:continueelif num < lts[-1]:n_l = self.binary_search(num, lts)lts[n_l] = numprint(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.
这篇关于leetcode-300 最长上升子序列 O(NlogN)解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
