华为OD机试真题——最小的调整次数/特异性双端队列（2025B卷：100分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

2025 B卷 100分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

2025华为OD真题目录+全流程解析/备考攻略/经验分享

华为OD机试真题《最小的调整次数/特异性双端队列》：

题目名称：最小的调整次数/特异性双端队列

题目描述

有一个特异性的双端队列，该队列可以从头部或尾部添加数据，但只能从头部移出数据。小A依次执行2n个指令（n个添加操作和n个移除操作）。添加指令按顺序插入1到n的数值（可能从头部或尾部添加），移除指令要求按1到n的顺序移出元素。在任何时刻可以调整队列数据顺序，求最少的调整次数以满足移除顺序要求。

输入描述

• 第一行输入整数n（1 ≤ n ≤ 3×10⁵）。
• 后续2n行包含n条添加指令（head add x或tail add x）和n条remove指令。

输出描述
输出一个整数，表示最小调整次数。

示例
输入：

5  
head add 1  
tail add 2  
remove  
head add 3  
tail add 4  
head add 5  
remove  
remove  
remove  
remove  

输出：

1  

解释：
移除顺序需为1→2→3→4→5。在第7步移除时队列头部为2，需调整顺序后移出，调整次数+1。

Java

问题分析

我们需要处理一个特异性的双端队列，每次添加元素可以选择头部或尾部，但只能从头部移除元素。目标是按顺序移除元素1到n，并在必要时调整队列顺序，求出最小的调整次数。

解题思路

1. 维护连续区间：跟踪当前连续的右边界 currentMax，表示当前连续递增序列的最大值。
2. 添加操作处理：如果添加的元素是 currentMax + 1 且添加到尾部，扩展连续区间；否则标记队列为无序。
3. 移除操作处理：若队列头部是当前期望值 expected，直接移除；否则调整队列，调整次数加一，并重置连续区间。

代码实现

import java.util.*;

public class Main {
   
    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();

        int expected = 1;
        int currentMax = 0;
        int adjusts = 0;
        boolean ordered = true;

        for (int i = 0; i < 2 * n; i++) {
   
            String line = sc.nextLine().trim();
            if (line.startsWith("remove")) {
   
                if (ordered && expected == currentMax) {
   
                    expected++;
                    currentMax = 0;
                } else {
   
                    adjusts++;
                    expected++;
                    currentMax = 0;
                    ordered = true;
                }
            } else {
   
                int x = Integer.parseInt(line.split(" ")[2]);
                if (ordered) {
   
                    if (x == currentMax + 1) {
   
                        currentMax = x;
                    } else {
   
                        ordered = false;
                        currentMax = Math.max(currentMax, x);
                    }
                } else {
   
                    currentMax = Math.max(currentMax, x);
                }
            }
        }

        System.out.println(adjusts);
    }
}

代码详细解析

1. 输入处理：读取n和后续的2n条指令。
2. 变量初始化：
   • expected：下一个需要移除的元素，初始为1。
   • currentMax：当前连续区间的最大值，初始为0。
   • adjusts：调整次数计数器。
   • ordered：标记队列是否处于有序状态。
3. 处理每条指令：
   • 移除指令：
     • 若队列有序且当前expected等于currentMax（即头部为expected），则直接移除。
     • 否则调整次数加一，重置currentMax并标记队列为有序。
   • 添加指令：
     • 若队列有序且新元素是currentMax + 1，扩展连续区间。
     • 否则标记队列为无序，并更新currentMax。

示例测试

示例输入：

5
head add 1
tail add 2
remove
head add 3
tail add 4
head add 5
remove
remove
remove
remove

输出：

1

解析：在第3步移除时队列头部不是1，调整次数加一。后续移除操作无需调整。

另一个测试用例：

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

输出：

2

解析：第一次移除时队列头部是3≠1，调整一次；第二次移除时头部是1≠2，调整第二次。

综合分析

1. 时间复杂度：O(n)，每个指令处理时间为O(1)。
2. 空间复杂度：O(1)，仅维护几个变量。
3. 优势：无需模拟队列操作，直接通过逻辑判断调整次数，高效处理大规模数据。
4. 适用性：适用于任何n值，尤其适合高并发和大数据场景。

python

问题分析

我们需要处理一个特异性的双端队列，队列可以从头部或尾部添加元素，但只能从头部移除元素。目标是按顺序移除1到n的元素，并在必要时调整队列顺序，求出最小的调整次数。

解题思路

1. 维护连续区间：跟踪当前连续的右边界 current_max，表示当前可连续移除的最大值。
2. 全局最大值：维护 global_max 记录所有已添加元素的最大值。
3. 调整条件：当需要移除的元素 expected 超过 current_max 时，必须调整队列，调整次数加一，并将 current_max 更新为 global_max。

代码实现

n = int(input())
expected = 1
current_max = 0