【leetcode 300】最长上升子序列 O(nlogn)解法

class Solution { //最长递增子序列 O(nlogn) 的解法 public int lengthOfLIS(int[] nums) { if(nums.length<=1) return nums.length; int[] minend = new int[nums.length+1]; //minend[i] 表示 长度为i的递增子序列的 末尾元素最小的值 int len = 0; //len指向minend的最后一个元素 minend[1] = nums[0]; len++; for(int i=1;i<nums.length;++i){ if(nums[i]>minend[len]) //说明 nums[i]的加入使得 现阶段的最长递增子序列的长度又向后扩展了一位 minend[++len] = nums[i]; else{ int pos = findFirstBiggerNum(minend,1,len,nums[i]); //查找minend中第一个等于或者大于nums[i]的数据的位置 并更新它 minend[pos] = nums[i]; } } return len; } //二分查找的递归实现 private int findFirstBiggerNum(int[] arr, int start, int end, int target) { if(start>=end){ if(arr[start]>=target) return start; else //必须保证arr[end] > target 才不会走到这条分支返回越界的值 return start+1; } int mid = (start+end)/2; if(arr[mid]<target) return findFirstBiggerNum(arr,mid+1,end,target); else if(arr[mid]==target) return mid; else return findFirstBiggerNum(arr,start,mid,target); }}