最小调整顺序次数（特异性双端队列）_第一行一个整数 n,表示数据范围。 接下来有 2n 行,其中有 n 行为添加数据:指令“

题目

有一个特异性的双端队列，该队列可以从头部到尾部添加数据，但是只能从头部移除数据。 小 A 一次执行 2n 个指令往队列中添加数据和移除数据， 其中 n 个指令是添加数据(可能从头部也可以从尾部添加) 依次添加 1 到 n , n 个指令是移出数据 现在要求移除数据的顺序为 1 到 n ， 为了满足最后输出的要求, 小 A 可以在任何时候调整队列中的数据的顺序 请问,小 A 最少需要调整几次才能满足移除数据的顺序正好是 1 到 n

输入

第一行一个整数 n ，表示数据范围 接下来有 2n 行,其中有 n 行为添加数据: 指令head add x表示从头部添加数据x tail add x表示从尾部添加数据x 另外 n 行为移除数据指令,指令为remove形式,表示移除一个数据 1≤n≤3×10^5105

输出

一个整数，表示小 A 要调整的最小次数

示例：

3
head add 1
remove
tail add 2
head add 3
remove
remove

输出：

1

 只需要调整1次，第二次remove需要将应该删除2，但是2在队尾，需要调整，然后再删除。

Java 代码

使用Deque

    public static void main(String[] args) {
        String[] ss = {"head add 1","remove","tail add 2","head add 3","remove","remove"};
        int count = 0;
        //删除索引，从1开始，每次删除一个，加一
        int delIndex = 1;
        Deque<Integer> deque = new ArrayDeque<>();
        for(String s : ss){
            if (s.startsWith("remove")){
                //如果只有一个元素，或者队列开头就是要删除的元素，直接操作
                if (deque.size() == 1 || deque.peekFirst() == delIndex){
                    deque.poll();
                    delIndex++;
                    continue;
                }
                //开始调整，转化为数组
                Object[] nums = deque.toArray();
                //排序
                Arrays.sort(nums);
                deque.clear();
                //写入deque
                for(Object obj:nums){
                    deque.addLast((Integer) obj);
                }
                deque.poll();
                delIndex++;
                count++;
            }
            else{
                String[] arr = s.split(" ");
                if (s.startsWith("head")){
                    deque.addFirst(Integer.parseInt(arr[2]));
                }
                else{
                    deque.addLast(Integer.parseInt(arr[2]));
                }
            }
        }
        System.out.println(count);
    }

使用List

    public static void main(String[] args) {
        String[] ss = {"head add 1","remove","tail add 2","head add 3","remove","remove"};
        int count = 0;
        int delIndex = 1;
        List<Integer> list = new ArrayList<>();
        for(String s : ss){
            if (s.startsWith("remove")){
                if (list.size() == 1 || list.get(0) == delIndex){
                    list.remove(0);
                    delIndex++;
                    continue;
                }
                Collections.sort(list);
                list.remove(0);
                delIndex++;
                count++;
            }
            else{
                String[] arr = s.split(" ");
                if (s.startsWith("head")){
                    list.add(0,Integer.parseInt(arr[2]));
                }
                else{
                    list.add(Integer.parseInt(arr[2]));
                }
            }
        }
        System.out.println(count);
    }