牛客4810合唱队：队列变换的最优解法
一、 问题理解
合唱队形要求队伍中有一个"峰顶"，使得峰顶左侧的同学身高严格递增，峰顶右侧的同学身高严格递减。我们的目标是在不改变同学相对位置的前提下，找出最少需要出列多少同学，使剩余同学满足这一条件。
二、解题思路
这个问题可以转化为寻找一个位置i，使得：
i左侧是一个严格递增序列
i右侧是一个严格递减序列
这样的序列长度尽可能长
这样，最少出列人数 = 总人数 - 最长合唱队形长度
三、动态规划解法
我们使用两个动态规划数组：
left[i]：表示以heights[i]结尾的最长递增子序列长度
right[i]：表示以heights[i]开头的最长递减子序列长度
对于每个位置i，合唱队形的最大长度为left[i] + right[i] - 1（减去重复计算的i位置）
四、算法步骤详解
初始化两个数组left和right，所有元素初始值为1
从左到右计算left数组：
对于每个i，检查前面所有比heights[i]小的元素j
更新left[i] = max(left[i], left[j] + 1)
从右到左计算right数组：
对于每个i，检查后面所有比heights[i]小的元素j
更新right[i] = max(right[i], right[j] + 1)
遍历所有位置，计算最大合唱队形长度
最少出列人数 = 总人数 - 最大合唱队形长度
五、完整代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/**
* 计算最少需要出列的同学数量，使剩余同学形成合唱队形
* @param heights 同学身高数组
* @return 最少需要出列的同学数量
*/
int minStudentsToRemove(vector<int>& heights) {
int n = heights.size();
if (n <= 2) return 0; // 少于3人不需要出列
vector<int> left(n, 1); // 从左到右的最长递增子序列长度
vector<int> right(n, 1); // 从右到左的最长递减子序列长度
// 计算从左到右的最长递增子序列
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (heights[j] < heights[i]) {
left[i] = max(left[i], left[j] + 1);
}
}
}
// 计算从右到左的最长递减子序列
for (int i = n - 2; i >= 0; --i) {
for (int j = n - 1; j > i; --j) {
if (heights[j] < heights[i]) {
right[i] = max(right[i], right[j] + 1);
}
}
}
int max_keep = 0;
// 计算每个位置作为峰值的最大保留人数
for (int i = 0; i < n; ++i) {
// 左右两边至少各1人才能形成合唱队形
if (left[i] >= 1 && right[i] >= 1) {
max_keep = max(max_keep, left[i] + right[i] - 1);
}
}
return n - max_keep;
}
int main() {
int n;
cin >> n;
vector<int> heights(n);
for (int i = 0; i < n; ++i) {
cin >> heights[i];
}
cout << minStudentsToRemove(heights) << endl;
return 0;
}六、优化思路
对于n较大的情况(接近3000)，可以考虑使用二分查找优化最长递增子序列的计算，将时间复杂度降低到O(nlogn)。
七、实际应用
这种算法不仅适用于合唱队形问题，还可以应用于其他需要寻找序列中特定模式的问题，如股票分析中的峰值检测、信号处理中的波形分析等。
原创内容 转载请注明出处
