题解 | #合唱队#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int[] height = new int[num];
        int[] maxLeft = new int[num];
        int[] maxRight = new int[num];
        int[] maxLength = new int[num];
        for(int i=0; i<num; i++){
            height[i] = in.nextInt();
        }
        /*算法思想类似于《蜘蛛纸牌》，相邻连续序列绑定作为一个整体，参与后续序列的比较，取最大值
            求解过程采用递归算法    */
        //先对两端点赋值，作为递归的起点
            maxLeft[0] = 0;
            maxRight[num - 1] = 0;
        // 右侧 递归必定要从最右端开始，否则找不到初值没办法往下进行
        // 120 150 200 160 130 140 120 110
        for(int i=num-1; i>=0; i--){
            for(int j=num-1; j>i; j--){
                if(height[i] > height[j]){
                    maxRight[i] = Math.max(maxRight[j] + 1, maxRight[i]);
                }
            }
        }
        // 左侧 递归必定要从最左端开始，否则找不到初值没办法往下进行
        // 120 150 200 160 130 140 120 110
        for(int i=0; i<num; i++){
            for(int j=0; j<i; j++){
                if(height[i] > height[j]){
                    maxLeft[i] = Math.max(maxLeft[j] + 1, maxLeft[i]);
                }
            }
        }
        //长度计算
        for(int i=0; i<num; i++){maxLength[i] = maxLeft[i] + maxRight[i] + 1;}
        System.out.print(num - getMax(maxLength));
        
}
public static int getMax(int[] a){
    int res = 0;
    for(int i :a){
        if(i>res) res = i;
    }
    return res;
}
}

（1）题目队列为双端队列，且可进行入队出队的操作，明确这两点就不会出现歧义

（2）开始我以为只能出队不能入队，导致做法简单但与题目结果不符

（3）可出可入将导致排序序列的元素可以不相邻，因此也提高了解题难度