题目主要信息

1、给出n个同学的身高，在不改变所有人的相对位置的情况下从中剔除几位，使得剩下的k*位同学的身高排序是形如：T1<T2<......<Ti-1Ti+1>......>TK 。

2、不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

3、求最少的出队人数

4、注意处理多组输入输出

方法一：动态规划

具体方法

分析题目可得，其实就是求最长递增子序列的变种题目，只不过加了一个约束条件，需要左边递增右边递减的情况。

1、先找到每一个位置i左侧的最长上升子序列长度left[i] 2、再找到每一个位置i右侧的最长下降子序列长度right[i] 3、然后求出所有位置的最长序列长度=左侧最长子序列长度+右侧最长子序列长度-1（因为该位置被算了两次，所以减1） 4、然后用数目减去最长序列长度就是答案，需要出队的人数

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            int[] left = new int[n]; //存储每个数左边小于其的数的个数
            int[] right = new int[n];//存储每个数右边小于其的数的个数
            left[0] = 1;            //最左边的数设为1
            right[n - 1] = 1;        //最右边的数设为1
            //计算每个位置左侧的最长递增
            for (int i = 0; i < n; i++) {
                left[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (arr[i] > arr[j]) {   //动态规划
                        left[i] = Math.max(left[j] + 1, left[i]);
                    }
                }
            }
            //计算每个位置右侧的最长递减
            for (int i = n - 1; i >= 0; i--) {
                right[i] = 1;
                for (int j = n - 1; j > i; j--) {
                    if (arr[i] > arr[j]) {   //动态规划
                        right[i] = Math.max(right[i], right[j] + 1);
                    }
                }
            }
            // 记录每个位置的值
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                //位置 i计算了两次 所以需要－1
                result[i] = left[i] + right[i] - 1; //两个都包含本身
            }

            //找到最大的满足要求的值
            int max = 1;
            for (int i = 0; i < n; i++) {
                max = Math.max(result[i],max);
            }
            System.out.println(n - max);
        }

    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，需要多次遍历数组，两层for循环嵌套
• 空间复杂度：$O(n)O(n)$，存每个位置的dp递增和递减数组。

方法二：借助二分查找

具体方法

由于直接使用动态规划，需要两次遍历数组，借助之前求解最长递增子序列的优化思想，借助二分查找来求解。用一个num数组记录以i为终点的从左向右和从右向走的子序列元素个数。

举例说明： 8 186 186 150 200 160 130 197 200

这里给出左侧遍历的结果，右侧是同样的道理。

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            int[] left = new int[n]; //存储每个数左边小于其的数的个数
            int[] right = new int[n];//存储每个数右边小于其的数的个数
            left[0] = arr[0];
            right[n - 1] = arr[n-1];
            int num[] =new  int [n];//记录以i为终点的从左向右和从右向走的子序列元素个数
            int index = 1;//记录当前子序列的长度
            for(int i=1;i<n;i++){
                if(arr[i]>left[index-1]){
                    //直接放在尾部
                    num[i] = index;//i左侧元素个数
                    left[index++] = arr[i];//更新递增序列
                }else {
                    //找到当前元素应该放在的位置
                    int low = 0,high = index-1;
                    while(low < high){
                        int mid = (low+high)/2;
                        if(left[mid] <arr[i])
                            low = mid + 1;
                        else
                            high = mid;
                    }
                    //将所属位置替换为当前元素
                    left[low] = arr[i];
                    num[i] = low;//当前位置i的左侧元素个数
                }
            }
            index = 1;
            for(int i=n-2;i>=0;i--){
                if(arr[i]>right[index-1]){
                     num[i] += index;
                     right[index++] = arr[i];
                }else {
                    int low = 0,high = index-1;
                    while(low < high){
                        int mid = (high+low)/2;
                        if(right[mid]<arr[i])
                            low = mid+1;
                        else
                            high = mid;
                    }
                    right[low] = arr[i];
                    num[i]+=low;
                }
            }
            int max = 1;
            for (int number: num )
                max = Math.max(max,number);
            // max+1为最大的k
            System.out.println(n - max);
        }
    }
}

复杂度分析

• 时间复杂度：$O(nlo{g}_2(n))O(nlog\_2(n))$，由于借助二分，少了一次遍历，所以是$lognlogn$
• 空间复杂度：$O(n)O(n)$，一个存左右子序列值的数组。