题目
这天蓝桥国王给他安排了 N 个对手，他们的战力值分别为 a1,a2,...,an， 且按顺序阻挡在小明的前方。对于这些对手小 明可以选择挑战，也可以选择避战。 身为高傲的骑士，小明从不走回头路，且只愿意挑战战力值越 来越高的对手。 请你算算小明最多会挑战多少名对手。
输入描述 输入第一行包含一个整数 N，表示对手的个数。 第二行包含 N 个整数 a1,a2,…,an，分别表示对手的战力 值。 1 ≤ N ≤ 3 x 10', 1 ≤ ai≤ 10°
输出描述
输出一行整数表示答案
题目来自南桥云课
解题
- 初始化一个只包含一个元素的空数组
tails和变量len作为当前最长递增子序列的长度。 - 使用
Scanner获取标准输入中的第一个整数n，表示后续会有n个整数输入。 - 检查
n是否小于等于零，如果是，则认为没有有效的序列，直接输出0并结束程序。 - 创建一个长度为
n的数组tails，初始化tails[0]为第一个输入的整数，表示初始状态下最长递增子序列的长度为1且结尾元素已知。 - 循环读取接下来的
n-1个整数，并对每个整数执行以下步骤：- 初始化两个指针
l和r分别指向tails数组的起始位置和当前位置。 - 使用二分查找方法在
tails数组中找到合适的插入位置，以便保持数组的升序排列。由于我们是在寻找第二大的数，所以当找到一个数curr大于等当前值时，我们需要向右移动l；反之，如果tails[mid]小于等于curr，则不需要改变l的位置。 - 在二分查找结束后，若
l等于len，意味着新的数curr是一个新的更大的数，应当被加到序列中，并增加len。 - 更新
tails[l]为curr的值。
- 初始化两个指针
- 最终，
len存储的就是所求的第二大的数出现的次数，即最长递增子序列的长度。
注意，在二分查找的过程中，我们需要检查 tails[mid] <= curr 而不是 tails[mid] < curr，因为我们希望找到的是不小于 curr 的最小下标，这样才能正确地记录第二大的数出现的位置。
此代码的核心思想在于维护一个有序数组 tails，它始终包含以当前读到的数为结尾的最长递增子序列的最大可能长度。这样，对于每一个新读入的整数，我们可以通过二分查找快速定位它在 tails 中的位置，进而更新 tails 并且统计第二大的数出现的次数。整个算法的时间复杂度为 O(n log n)。
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 边界条件判断：如果序列长度为0或负数，则直接返回0
if (n <= 0) {
System.out.println(0);
return;
}
long[] tails = new long[n]; // tails[i] 表示长度为 i+1 的最长递增子序列的结尾元素
int len = 0; // 当前最长递增子序列的长度
tails[0] = sc.nextLong();
for (int i = 1; i < n; i++) {
long curr = sc.nextLong();
int l = 0, r = len;
// 二分查找当前元素应该插入的位置
while (l < r) {
int mid = l + (r - l) / 2;
if (tails[mid] <= curr) {
l = mid + 1;
} else {
r = mid;
}
}
// 如果找到了位置，更新该位置的值
if (l == len) {
len++;
}
tails[l] = curr;
}
// 输出最长递增子序列的长度
System.out.println(len);
sc.close();
}
}练习
当然可以，这里有一些类似的问题供您练习：
给定一个正整数 n，求 1 到 n 的所有整数中，不含数字 9 的有多少个？
- 输入：n (1 <= n <= 10^9)
- 输出：符合条件的整数个数
给定一个字符串 s，找出 s 中最长的有效括号子串长度。
- 输入：s (长度 <= 10^5)
- 输出：最长有效括号子串长度
给定一个非负整数数组 nums ，你最初位于数组的第一个索引。 数组中的每个元素代表你在该位置上的最大跳跃步数。 你的目标是使用最少的跳跃次数到达数组的最后一个索引。 假设你总是可以到达数组的最后一个索引。
- 输入：nums (长度 <= 10^6)
- 输出：最少跳跃次数
给定一个二叉树，判断它是否是完全二叉树。
- 输入：二叉树节点个数、根节点和左/右子节点的关系
- 输出：布尔值，表示是否为完全二叉树
设计一个数据结构支持以下操作：
insert(val)：将 val 插入到字典中。
delete(key)：删除键 key 对应的值。
find(minimum)：返回当前字典中的最小键。
find(maximum)：返回当前字典中的最大键。
find(value)：返回键 value 对应的所有键。
count：返回字典中元素的总数。
empty：返回字典是否为空。
size：返回字典的大小。
输入：一系列操作及其参数
输出：针对每个操作的操作结果
