Longest Increasing Subsequence

FullStackDeveloper 發(fā)布于2019-08-14 17:23 / 1721人閱讀

摘要：題目鏈接主要兩種方法和用，就是每次找出為結(jié)尾的最長的串的長度就好了。所以分解成就是，這個(gè)復(fù)雜度是。用一個(gè)數(shù)組，表示的長度為，表示長度為的，最右邊的可能的最小值。這里只要求長度即可，那就直接用就可以了，整個(gè)用個(gè)數(shù)組就行了。

Longest Increasing Subsequence

題目鏈接：https://leetcode.com/problems...

主要兩種方法：dp和greedy

dp：用dp table，就是每次找出nums[i]為結(jié)尾的最長的increasing串的長度就好了。所以分解成subproblem就是: dp[i] = max(dp[j]) + 1，這個(gè)復(fù)雜度是O(N^2)。

然后就是greedy + binary search的方法，改進(jìn)NlogN。用一個(gè)數(shù)組min[i]，i表示increasing sequence的長度為i，min[i]表示長度為i的increasing sequence，最右邊的num可能的最小值。整個(gè)是patient sort的思路。
http://www.cs.princeton.edu/c...

stack的top元素按從小到大的順序所以可以binary search。如果允許重復(fù)且重復(fù)的算在increasing sequence里面，那么重復(fù)的element就加到比它大的那個(gè)top下面就好了。如果重復(fù)的不算的話，就每次找>=的地方，查一下是否是重復(fù)，是就不加，不是就往里面加。
如果求路徑就加個(gè)parent point的輔助數(shù)組。這里只要求長度即可，那就直接用top（min）就可以了，整個(gè)用個(gè)數(shù)組就行了。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        /* greedy + binary search
         * min[i]: minimum rightmost element in increasing sequence with length = i + 1
         */
         int[] min = new int[nums.length+1];
         min[0] = nums[0];
         int index = 0;
        for(int i = 1; i < nums.length; i++) {
            // new one >= rightmost one, increase the length of sequence
            if(nums[i] > min[index]) {
                min[++index] = nums[i];
            }
            // new one < leftmost, update the leftmost
            else if(nums[i] <= min[0]) {
                min[0] = nums[i];
            }
            // new one between [0, index + 1], find the place k that
            // min[k-1] < nums[i] <= min[k], update min[k]
            else {
                int k = binarySearch(min, nums[i], 0, index);
                min[k] = nums[i];
            }
        }
        return index + 1;
    }
    
    private int binarySearch(int[] min, int x, int l, int r) {
        while(l + 1 < r) {
            int mid = l + (r - l) / 2;
            if(min[mid] >= x) r = mid;
            else l = mid;
        }
        if(min[l] >= x) return l;
        return r;
    }
}