抽象思维
。没有抽象思维,所有的题目对你来说都是新题。你无法将之前做题的经验迁移到这道题,那你做的题意义何在?抽象思维
。注意。 本文是帮助你识别套路,从横向上理清解题的思维框架,并没有采用最优解,所有的题目给的解法都不是最优的,但是都可以通过所有的测试用例。如果你想看最优解,可以直接去讨论区看。或者期待我的深入剖析系列
。
美团和华为都考了这个题。
如果 i < j 则 nums[i] < nums[j]
。问:一次可以挑选最多满足条件的数字是多少个。dp[i] = dp[j] + 1 (其中 i > j, nums[i] > nums[j])
[10, 9, 2, 5, 3, 7, 101, 18]
为例,当我们计算到 dp[5]的时候,我们需要往回和 0,1,2,3,4 进行比较。[ [1,2], [2,3], [3,4] ]
。就是第一个区间的 2 小于等于 第二个区间的 2,第二个区间的 3 小于等于第三个区间的 3。前面区间的结束
和后面区间的开始
结合起来看,其就是一个非严格递增序列。而我们的目标就是删除若干区间,从而剩下最长的非严格递增子序列。这不就是上面的题么?只不过上面是严格递增,这不重要,就是改个符号的事情。 上面的题你可以看成是删除了若干数字,然后剩下剩下最长的严格递增子序列。 这就是抽象的力量,这就是套路。这道题还有一种贪心的解法,其效率要比动态规划更好,但由于和本文的主题不一致,就不在这里讲了。
435. 无重叠区间
是换皮题,唯一的区别这里又变成了严格增加。没关系,我们把等号去掉就行了。并且由于这道题求解的是最长的长度,因此转化也不需要了。当然,这道题也有一种贪心的解法,其效率要比动态规划更好,但由于和本文的主题不一致,就不在这里讲了。
646. 最长数对链
一模一样了,不用我多说了吧?当然,这道题也有一种贪心的解法,其效率要比动态规划更好,但由于和本文的主题不一致,就不在这里讲了。
小任务:请尝试使用贪心在 NlogN 的时间内完成算法。(参考我上面的代码就行)