关于leetcode300复杂度nlogn方法
来源：9-8 LIS问题 Longest Increasing Subsequence
v不离不弃v
2020-05-19
波波老师-。-the best way to solve LIS problem 那个解法，我看一1个多小时，还是没明白-。-没办法了，波波老师，有空能详细讲下思路嘛，我怎么感觉这个解法像是贪心算法呀-。-虽然我还没学到那个，但是真的是看不懂，请问前面动态规划的方法懂了，这个方法还必须要理解么？
题外话：还有波波老师，我感觉这题用memory search的 方法完全是和这一题dp方法的一模一样呀，还变复杂了许多，个人觉得这一题只需要侧重于了解dp的方法就好了？memory search的方法相当于巩固dp了-。-老师您觉得我想的对不？
1回答
-
liuyubobobo
2020-05-19
在这个程序中，我们的状态定义变了。dp[i] 表示的是使用 nums 可以构成的长度为 i 的上升子序列的最后一个元素最小可以是谁。
为什么找最小？因为我们希望子序列尽量长，所以长度为 i 的序列的最后一个元素，应该尽量小，这样才方便添加一个新的元素在后面，后成一个更长的，长度为 i + 1 的上升子序列。
初始的时候，dp[1] = nums[0]，也就是初始的时候，我们只看 nums[0]，它一个人构成了一个长度为 1 的上升子序列。
下面的循环是依次看其他的元素。如果这个元素比现在找到的最长的上升子序列的最后一个元素还要大，那么我们把这个元素放在后面，就找到了一个更长的上升子序列。这个更长的上升子序列，最后一个元素就是这个新的 nums[i]。对应下面的代码：
if(nums[i] > dp[len]){ len ++; dp[len] = nums[i]; }否则的话，我们看一下，这个元素能不能构成某个长度的子序列的一个更小的末尾元素？怎么找到这个位置呢？这里要注意，因为 dp[1].... dp[len-1] 一定是有序的，所以我们可以使用二分查找，找到这个位置。我的 C++ 代码中, lower_bound 实际上就是在使用标准库，找到第一个大于等于这个位置的元素。这个问题我提供了 Java 代码，你可能看起来更清晰一些：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0300-Longest-Increasing-Subsequence/java-0300/src/Solution3.java
找到这个位置以后，如果这个位置的元素比 nums[i] 还要大，我们就能用这个更小的 nums[i] 来更新这个位置。对应我的 C++ 代码中下面的过程：
最后，len 就是结果。注意，结果没有存在 dp 数组中。可以再回忆一下，我们定义的 dp[i] 到底是什么意思，这很重要。
P.S.
没问题，觉得 dp 更好理解，了解 dp 就够了：）
继续加油！：）
00
相似问题