LeetCode[300] Longest Increasing Subsequence

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.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

BinarySearch + 替换

复杂度

思路

对于排好序的数组，尽量用较小的值去替换已经排好序的数组中的值。因为要找的是最长的序列，所以每次将排好序的数组中替换成已经排好序的，会能保证得到的结果是最长的。

代码

// O(NlgN) public int lengthOfLIS(int[] nums) {    int len = 0;    int[] a = new int[nums.length];    for(int val : nums) {        int index = binary(a, 0, len - 1, val);        a[index] = val;        // 说明这个数字是新加进去这个数组的        if(len == index) len ++;    }    return len;}// 相当于在left-right的区间内找到val的插入位置。保证升序；public int binary(int[] a, int left, int right, int val) {    while(left <= right) {        int mid = getMid(left, right);        if(a[mid] >= val) {            right = mid - 1;        }        // 相等也要替换这个值;        else {            left = mid + 1;        }    }    return left;}public int getMid(int left, int right) {    return left + (right - left) / 2;}