时间复杂度为O(nlogn)的求最长递增子序列的解法

Dear 丶 2023-10-12 17:27 5阅读 0赞

题目 ： [LeetCode 300. Longest Increasing Subsequence][]  
比较容易的动态规划解法的时间复杂度为O(n^2)。被提示有O(nlogn)的，想不出来，看别人的Solution里提到了普林斯顿大学的资料：[https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf][https_www.cs.princeton.edu_courses_archive_spring13_cos423_lectures_LongestIncreasingSubsequence.pdf]，才做出来（[ac代码][ac]）。大神太厉害：  
![在这里插入图片描述][1db036e903644d70b2f7d56f6102cc91.png]  
![在这里插入图片描述][8348ad3164274a2a82579fcd712c6e08.png]  
![在这里插入图片描述][cdf511ebf42448e6bb762c4d00f28729.png]  
![在这里插入图片描述][d6721a8a19414a09bf2e279200c519f5.png]  
![在这里插入图片描述][49e48c7b40b848609eb936ea53c58923.png]

[LeetCode 300. Longest Increasing Subsequence]: https://leetcode.com/problems/longest-increasing-subsequence/description/
[https_www.cs.princeton.edu_courses_archive_spring13_cos423_lectures_LongestIncreasingSubsequence.pdf]: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf
[ac]: https://leetcode.com/problems/longest-increasing-subsequence/submissions/973945421/
[1db036e903644d70b2f7d56f6102cc91.png]: https://img-blog.csdnimg.cn/1db036e903644d70b2f7d56f6102cc91.png
[8348ad3164274a2a82579fcd712c6e08.png]: https://img-blog.csdnimg.cn/8348ad3164274a2a82579fcd712c6e08.png
[cdf511ebf42448e6bb762c4d00f28729.png]: https://img-blog.csdnimg.cn/cdf511ebf42448e6bb762c4d00f28729.png
[d6721a8a19414a09bf2e279200c519f5.png]: https://img-blog.csdnimg.cn/d6721a8a19414a09bf2e279200c519f5.png
[49e48c7b40b848609eb936ea53c58923.png]: https://img-blog.csdnimg.cn/49e48c7b40b848609eb936ea53c58923.png