1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
|
import java.util.Arrays; import java.util.HashMap;
public class {
public int lengthOfLIS(int[] nums) {
HashMap<Integer, Integer> m = new HashMap<>();
int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp, Integer.MAX_VALUE); int t = 0;
for (int i = 0; i < n; i++) { int idx = binarySearch(dp, 0, i, nums[i]); dp[idx] = nums[i]; if (idx == t) { t++; } } return t; }
public int binarySearch(int[] nums, int left, int right, int target){ while(left <= right){ int mid = left + ((right - left) >> 1); if (nums[mid] == target) return mid; else if (nums[mid] > target) left = mid -1; else right = mid + 1; } return left; } }
|
近期评论