有点问题需要考虑等于情况 public class Solution { public int[] LIS (int[] arr) { int[] nums = new int[arr.length]; int[] temp = new int[arr.length]; nums[0] = 1; int tempIndex = 0; temp[tempIndex] = arr[0]; for (int i = 1; i < arr.length; ++i) { int left = 0, right = tempIndex; if (arr[i] > temp[tempIndex]) { ++tempIndex; nums[i] = tempIndex + 1; temp[tempIndex] = arr[i]; } else { while (left <= right) { // 注意这里 left <= right 而不是 left < right，我们要替换的是第一个比 arr[i] 大的元素 int mid = (right + left) / 2; if (temp[mid] > arr[i]) { right = mid - 1; } else { left = mid + 1; } } if(left>0&&temp[left-1]==arr[i]){ left--; } temp[left] = arr[i]; nums[i] = left + 1; } } int[] res = new int[tempIndex + 1]; for (int i = nums.length - 1; i >= 0; --i) { if (nums[i] == tempIndex + 1) { res[tempIndex] = arr[i]; --tempIndex; } } return res; } }