O(nlgn) java solution


  • 0
    S
    public class Solution {
        public int lengthOfLIS(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
            int m = nums.length;
            int[] res = new int[m + 1];
            res[1] = nums[0];
            int len = 1;
            for (int i = 1; i < m; i++) {
                if (nums[i] > res[len]) {
                    res[++len] = nums[i];
                } else if (nums[i] < res[0]) {
                    res[0] = nums[i];
                } else if (nums[i] > res[0] && nums[i] < res[len]) {
                    int index = BinarySearch(res, 0, len, nums[i]);
                    res[index] = nums[i];
                }
            }
            return len;
        }
        // find the largest smallest one(may have the same element(only once))
        private int BinarySearch(int[] res, int left, int right, int target) {
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (res[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return right;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.