题解 | #合唱队#

动态规划+二分

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 nums[] = new int[n];
            for(int i = 0; i < n;i++) {
                nums[i] = sc.nextInt();
            }
            int out = singQueue(nums, n);
            System.out.println(out);
        }
    }

    public static int singQueue(int[] nums, int n) {
        int[] left = new int[n];
        int[] right = new int[n];
        List<Integer> dp = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            if(dp.isEmpty() || nums[i] > dp.get(dp.size()-1)) {
                dp.add(nums[i]);
                left[i] = dp.size();
            }else if(nums[i] <= dp.get(dp.size()-1)){
                int pos = lowerBound(dp, nums[i]);
                dp.set(pos, nums[i]);
                left[i] = pos + 1;
            }
        }
        dp.clear();
        for(int i = n-1; i >= 0; i--) {
            if(dp.isEmpty() || nums[i] > dp.get(dp.size()-1)) {
                dp.add(nums[i]);
                right[i] = dp.size();
            }else if(nums[i] <= dp.get(dp.size()-1)){
                int pos = lowerBound(dp, nums[i]);
                dp.set(pos, nums[i]);
                right[i] = pos + 1;
            }
        }
        int max = 0;
        for(int i = 0; i<n;i++) {
            max= Math.max(left[i] + right[i], max);
        }
        return n - max + 1;

    }

    public static int lowerBound(List<Integer> dp, int key) {
        int l = 0, r = dp.size() - 1;
        while(l  < r) {
            int mid = (l + r) / 2;
            if(key <= dp.get(mid)) {
                r = mid;
            }else {
                l = l + 1;
            }
        }
        return r;
    }
}