2025 B卷 100分 題型

本文涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、測試用例以及綜合分析；
并提供Java、python、JavaScript、C++、C語言、GO六種語言的最佳實現方式！

2025華為OD真題目錄+全流程解析/備考攻略/經驗分享

華為OD機試真題《最小的調整次數/特異性雙端隊列》：

---

---

題目名稱：最小的調整次數/特異性雙端隊列

---

屬性	內容
知識點	雙端隊列、邏輯處理
時間限制	1秒
空間限制	256MB
限定語言	不限

---

題目描述

有一個特異性的雙端隊列，該隊列可以從頭部或尾部添加數據，但只能從頭部移出數據。小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