牛客-合唱队解法
描述
牛客网题目: 合唱队 N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。 通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
例子
123 124 125 123 121 是一个合唱队形
123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
注意：不允许改变队列元素的先后顺序且不要求最高同学左右人数必须相等
数据范围：1≤n≤3000
输入描述
用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开
输出描述
最少需要几位同学出列
示例
- 示例1
输入：
8 186 186 150 200 160 130 197 200
输出：
4
说明：
由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130
思路
解法一: 动态规划
分析题目可得，其实就是求最长递增子序列的变种题目，只不过加了一个约束条件，需要左边递增右边递减的情况。
- 状态定义：
- left[i]表示该位置结尾的最长递增子序列长度，
- right[i]表示该位置开头的最长递减子序列长度。
- 状态初始化：初始长度均为1。
- 状态转移：
- 正序遍历时，如果i位置同学身高大于j位置同学，则可以排在j位置同学后面，即left[i]=Math.max(left[i],left[j]+1)。
- 逆序遍历时，如果i位置同学身高大于j位置同学，则j可排在i同学后面，构成递减子序列，即right[i]=Math.max(right[i],right[j]+1)。
步骤
- 先找到每一个位置i左侧的最长上升子序列长度left[i]
- 再找到每一个位置i右侧的最长下降子序列长度right[i]
- 然后求出所有位置的最长序列长度=左侧最长子序列长度+右侧最长子序列长度-1（因为该位置被算了两次，所以减1）
- 然后用数目减去最长序列长度就是答案，需要出队的人数
代码示例
public static void dp() {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
// //计算每个位置左侧的最长递增
int[] left = new int[n];
Arrays.fill(left, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
left[i] = Math.max(left[i], left[j] + 1);
}
}
}
// //计算每个位置右侧的最长递减
int[] right = new int[n];
Arrays.fill(right, 1);
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
right[i] = Math.max(right[i], right[j] + 1);
}
}
}
// 统计每个位置的合唱队形长度最大值
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, left[i] + right[i] - 1);
}
System.out.println(n - max);
}
}
解法二: 二分查找
步骤
- 新建left数组和right数组，left[i]表示该位置结尾的最长递增子序列长度，right[i]表示该位置开头的最长递减子序列长度。
- 然后维护一个递增数组tail1，如果tail1数组为空，或arr[i]大于tail1数组末尾元素，直接将arr[i]放在tail1数组末尾，tail1数组的长度即是当前位置结尾的最长递增子序列长度。否则，二分法找到arr[i]在tail1数组中的位置， 假设该位置为l，则l+1为当前位置结尾的最长递增子序列长度。
- 对于right数组，逆序遍历arr数组，维护一个递增数组tail2，如果tail2数组为空，或arr[i]大于tail2数组末尾元素，直接将arr[i]放在tail2数组末尾，tail2数组的长度即是当前位置开头的最长递减子序列长度。否则，二分法找到arr[i]在tail2数组中的位置，假设该位置为l，则l+1为当前位置开头的最长递减子序列长度。
- 最后，遍历left、right数组，统计每个位置的合唱队形长度最大值。
代码示例
public static void binarySearch() {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
// 记录i结尾的最长递增子序列长度
int[] left = new int[n];
// 记录递增数组
int[] tail1 = new int[n];
int idx = -1;
for (int i = 0; i < n; i++) {
if (i == 0 || tail1[idx] < arr[i]) {
tail1[++idx] = arr[i];
left[i] = idx + 1;
} else { // 二分查找 arr[i] 在tail1中的位置
int l = 0, m = 0, r = idx;
while (l < r) {
m = (l + r) / 2;
if (arr[i] > tail1[m]) {
l = m + 1;
} else {
r = m;
}
}
tail1[l] = arr[i];
left[i] = l + 1;
}
}
// 记录i结尾的最长递减子序列长度
int[] right = new int[n];
int[] tail2 = new int[n];
int idx2 = -1;
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1 || arr[i] > tail2[idx2]) {
tail2[++idx2] = arr[i];
right[i] = idx2 + 1;
} else {
int l = 0, m = 0, r = idx2;
while (l < r) {
m = (l + r) / 2;
if (arr[i] > tail2[m]) {
l = m + 1;
} else {
r = m;
}
}
tail2[l] = arr[i];
right[i] = l + 1;
}
}
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, left[i] + right[i] - 1);
}
System.out.println(n - max);
}
}