AcWing 896. 最长上升子序列 II
原题链接
中等
作者:
icu666
,
2022-02-18 04:42:12
,
所有人可见
,
阅读 126
构造一个队列, 保存各个长度下的最小队尾元素值: [1, 2, 5, 6]
当枚举到新的元素t时, 查找队列中 >= t 的位置, 替换为t
队列长度即为上升子序列的最大长度
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in) ;
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
int len = indexOf(list, nums[i]);
if (len == list.size()) {
list.add(nums[i]);
} else {
list.set(len, nums[i]);
}
}
System.out.println(list.size());
}
//find the index of a num >= t
public static int indexOf(List<Integer> list, int t) {
int i = 0;
int j = list.size();
while (i < j) {
int mid = i + (j - i) / 2;
if (list.get(mid) < t) {
i = mid + 1;
} else {
j = mid;
}
}
return i;
}
}