Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
这道题目，常规解法O(n2)没有难度，关键比较有意思的解题方式在于二分查找O(nlgn).
用一个数组tails，tails[i]的意思表示长度为i+1的LIS的末尾最小数。比如数组[2,3,5,4]长度为1的LIS最小的为2，那么tails[0]=2,长度为2的LIS有2，3和3，5末尾最小为3，所以tails[1]=3。以此类推有tails[2]=4。
反证可以确定，tails数组中的元素一定是有序递增的。所以可以在tails数组中进行二分查找：从前往后遍历输入的数组，查找大于当前数n的最小数的位置：如果找到了，那么表明该长度的LIS最小末尾该被替换；如果没有找到，则可以将n放置在原来最长LIS的后面组成一个长度加一的LIS。相当于动态生成了上面的tails数组。
代码如下：
public class Solution { public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; int len = 0; for (int n : nums) { int l = 0,r = len; while (l != r) { int mid = (l + r) / 2; if (tails[mid] < n) l = mid + 1; else r = mid; } tails[l] = n; if (l == len) len ++; } return len; }}新闻热点
疑难解答
