Wednesday, September 13, 2017

[LeetCode]Increasing Triplet Subsequence


想假设寻找是否存在长度为2的IS(increasing subsequence)怎么做。从左向右扫,维护最小值,然后看当前数是否比维护的最小值大,如果是的话我们就验证数组中有长度为2的IS。如果数组中存在IS,这个方法一定能够验证,因为假设存在递增序列n[i], n[j],假设n[i]不是从n[0]到n[j]的最小值,我们一定找到了更小的从而验证了n[j]结尾的递增序列。如果n[i]是最小值,那我们就找到了递增序列。那么对于长度为3的IS,我们依次类推,DP[i]表示长度为i的IS结尾的最小值,如果DP[i]不存在则代表不存在长度为i的IS,因为,我们找到了长度为i - 1的IS的结尾的最小值m,m在每一时刻可能不相同,但是我们在数组的任何位置都无法找到大于当前m的值,也就是说数组的任何位置都不可能为长度为i的IS的结尾,所以其不存在。那么我们如何更新DP呢,如果当前数n比DP的最后一个数e(当前最长IS结尾的最小数)大,则我们可以找到更长的IS,我们将n加入DP的末尾,否则我们将DP当中大于n的最小值更新为n,代表我们找到了更小的某长度的IS的结尾。很显然对于这一题,我们只需要判断DP在某一时间size是否为3,代表存在ITS,时间复杂度O(n),常数空间,代码如下:



No comments:

Post a Comment