题目的主要信息：

• 给出$nn$个同学的身高，在不改变所有人的相对位置的情况下从中剔除几位，使得剩下的$kk$位同学的身高排序是形如：
• 这里是必须是严格大小于，不要求最高同学左右人数必须相等
• 求最少的出队人数
• 注意处理多组输入输出

方法一：动态规划

具体做法：

要使出队的同学数最少，意味着留下来的同学数量最多，我们可以用动态规划来求留下来的同学最多的数量。

我们可以用$dp1[i]dp1[i]$表示从左到右以第$ii$个同学为结尾的最长递增序列有多长，用$dp2[i]dp2[i]$表示从右到左以第$ii$个同学为结尾的最长递增序列有多长，那我们遍历数组，对于每个元素，查看其左边和右边，它就是最大的元素，我们将两个dp加起来减1，就是以它为最高人的队列有多少人，我们取这个的最大值，再用$nn$减去最大值就是出队最少人数。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        vector<int> queue(n);
        for(int i = 0; i < n; i++) //身高输入队列
            cin >> queue[i];
        vector<int> dp1(n, 1);
        vector<int> dp2(n, 1);
        for(int i = 0; i < n; i++){ //从左到右求每位为止的最长递增长度
            for(int j = i - 1; j >= 0; j--)
                if(queue[i] > queue[j])
                    dp1[i] = max(dp1[j] + 1, dp1[i]);
        }
        for(int i = n - 1; i >= 0; i--){ //从右到左求到每位为止的最长递增长度
            for(int j = i + 1; j < n; j++)
                if(queue[i] > queue[j])
                    dp2[i] = max(dp2[j] + 1, dp2[i]);
        }
        int max = -1;
        for(int i = 0; i < n; i++){
            if(dp1[i] + dp2[i] > max) //二者相加的最大值
                max = dp1[i] + dp2[i];
        }
        cout << n - max + 1 << endl; //不能直接取二者相加，中间个元素会重复
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，统计dp数组中用了两层循环
• 空间复杂度：$O(n)O(n)$，dp数组的长度为$nn$

方法二：二分法改进

具体做法：

我们可以在遍历数组的时候，用一个help数组有序的记录前面的数字，用二分法查找第一个大于等于当前遍历元素的下标，该下标距离初始的值就是当前dp的值，并用这个较小值替代help数组中的它，如果它比整个help数组都大，就将其加到help数组末尾，增加这个的长度。

为什么能用较小值替换呢，因为比它小的它都能大于，刚好可以表达长度，比它大的因为出现在前面，跟他没有关系，但是如果后面出现了一个更大，它明显比比它更大的数能够拥有更多的递增长度，可以看下图从左到右计算：

从右到左与这个类似，不再赘述。后续同方法一，遍历找到相加的最大值。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        vector<int> queue(n);
        for(int i = 0; i < n; i++) //身高输入队列
            cin >> queue[i];
        vector<int> dp1(n);
        vector<int> dp2(n);
        vector<int> help;
        for(int i = 0; i < n; i++){
            //二分查找第一个大于或者等于遍历到的这个数的
            int temp = lower_bound(help.begin(), help.end(), queue[i]) - help.begin();
            dp1[i] = temp + 1;
            if(temp < help.size())  //将较小的值插入
                help[temp] = queue[i];
            else //新加入
                help.push_back(queue[i]);
        }
        help.clear();
        for(int i = n - 1; i >= 0; i--){
            //二分查找
            int temp = lower_bound(help.begin(), help.end(), queue[i]) - help.begin();
            dp2[i] = temp + 1;
            if(temp < help.size()) 
                help[temp] = queue[i];
            else
                help.push_back(queue[i]);
        }
        int max = -1;
        for(int i = 0; i < n; i++){
            if(dp1[i] + dp2[i] > max) //二者相加的最大值
                max = dp1[i] + dp2[i];
        }
        cout << n - max + 1 << endl; //不能直接取二者相加，中间个元素会重复
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，二分查找每次复杂度为$O(lo{g}_{2}n)O(log\_2n)$，一共查找$O(n)O(n)$次
• 空间复杂度：$O(n)O(n)$，三个辅助数组长度都不会超过$nn$