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.
這道題目，常規(guī)解法O(n2)沒有難度，關(guān)鍵比較有意思的解題方式在于二分查找O(nlgn).
用一個數(shù)組tails，tails[i]的意思表示長度為i+1的LIS的末尾最小數(shù)。比如數(shù)組[2,3,5,4]長度為1的LIS最小的為2，那么tails[0]=2,長度為2的LIS有2，3和3，5末尾最小為3，所以tails[1]=3。以此類推有tails[2]=4。
反證可以確定，tails數(shù)組中的元素一定是有序遞增的。所以可以在tails數(shù)組中進(jìn)行二分查找：從前往后遍歷輸入的數(shù)組，查找大于當(dāng)前數(shù)n的最小數(shù)的位置：如果找到了，那么表明該長度的LIS最小末尾該被替換；如果沒有找到，則可以將n放置在原來最長LIS的后面組成一個長度加一的LIS。相當(dāng)于動態(tài)生成了上面的tails數(shù)組。
代碼如下：
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; }}新聞熱點
疑難解答
