華為OD機試真題——最小的調整次數/特異性雙端隊列（2025A卷：100分）Java/python/JavaScript/C++/C語言/GO六種最佳實現

在這里插入圖片描述

2025 A卷 100分題型

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

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

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

- 題目名稱：最小的調整次數/特異性雙端隊列
- - 題目描述
- Java
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- python
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- JavaScript
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- C++
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- C語言
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- GO
- - 問題分析
  - 解題思路
  - 代碼實現
  - 代碼詳細解析
  - 示例測試
  - 綜合分析
- 更多內容：

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

屬性	內容
知識點	雙端隊列、邏輯處理
時間限制	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→2→3→4→5。在第7步移除時隊列頭部為2，需調整順序后移出，調整次數+1。

Java

問題分析

我們需要處理一個特異性的雙端隊列，每次添加元素可以選擇頭部或尾部，但只能從頭部移除元素。目標是按順序移除元素1到n，并在必要時調整隊列順序，求出最小的調整次數。

解題思路

維護連續區間：跟蹤當前連續的右邊界 currentMax，表示當前連續遞增序列的最大值。
添加操作處理：如果添加的元素是 currentMax + 1 且添加到尾部，擴展連續區間；否則標記隊列為無序。
移除操作處理：若隊列頭部是當前期望值 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);}
}

代碼詳細解析

輸入處理：讀取n和后續的2n條指令。
變量初始化：
- expected：下一個需要移除的元素，初始為1。
- currentMax：當前連續區間的最大值，初始為0。
- adjusts：調整次數計數器。
- ordered：標記隊列是否處于有序狀態。
處理每條指令：
- 移除指令：
  - 若隊列有序且當前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

輸出：

解析：在第3步移除時隊列頭部不是1，調整次數加一。后續移除操作無需調整。

另一個測試用例：

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

輸出：

解析：第一次移除時隊列頭部是3≠1，調整一次；第二次移除時頭部是1≠2，調整第二次。

綜合分析

時間復雜度：O(n)，每個指令處理時間為O(1)。
空間復雜度：O(1)，僅維護幾個變量。
優勢：無需模擬隊列操作，直接通過邏輯判斷調整次數，高效處理大規模數據。
適用性：適用于任何n值，尤其適合高并發和大數據場景。

python

問題分析

我們需要處理一個特異性的雙端隊列，隊列可以從頭部或尾部添加元素，但只能從頭部移除元素。目標是按順序移除1到n的元素，并在必要時調整隊列順序，求出最小的調整次數。

解題思路

維護連續區間：跟蹤當前連續的右邊界 current_max，表示當前可連續移除的最大值。
全局最大值：維護 global_max 記錄所有已添加元素的最大值。
調整條件：當需要移除的元素 expected 超過 current_max 時，必須調整隊列，調整次數加一，并將 current_max 更新為 global_max。

代碼實現

n = int(input())
expected = 1
current_max = 0
global_max = 0
adjusts = 0for _ in range(2 * n):line = input().strip()if line.startswith('remove'):if expected > current_max:adjusts += 1current_max = global_maxexpected += 1else:x = int(line.split()[2])global_max = max(global_max, x)if x == current_max + 1:current_max = xprint(adjusts)

代碼詳細解析

輸入處理：讀取 n 和后續的2n條指令。
初始化變量：
- expected：下一個需要移除的元素，初始為1。
- current_max：當前連續區間的最大值，初始為0。
- global_max：所有已添加元素的最大值，初始為0。
- adjusts：調整次數計數器。
處理指令：
- 移除指令：若 expected 超過 current_max，調整次數加一，current_max 設為 global_max，隨后 expected 遞增。
- 添加指令：更新 global_max，若元素是 current_max + 1，擴展連續區間。
輸出結果：打印總調整次數。

示例測試

示例輸入：

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

輸出：

解析：

前三次操作后，current_max=2，expected=2。
添加3、4、5后，current_max 保持2，global_max=5。
第四次移除時，expected=3 > current_max=2，調整次數加一，current_max 設為5，后續移除無需調整。

另一個測試用例：

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

輸出：

解析：

首次移除時，expected=1 > current_max=0，調整一次。
第二次移除時，expected=2 > current_max=3（調整后 current_max=3），調整第二次。

綜合分析

時間復雜度：O(n)，每個指令處理時間為O(1)。
空間復雜度：O(1)，僅維護幾個變量。
優勢：無需模擬隊列操作，通過維護連續區間和全局最大值高效判斷調整條件。
適用場景：適用于大規模數據，時間復雜度為線性，滿足題目約束。

JavaScript

問題分析

我們需要處理一個特異性的雙端隊列，隊列可以從頭部或尾部添加元素，但只能從頭部移除元素。目標是在執行一系列添加和移除操作后，統計最小的調整次數，使得移除順序為1到n。

解題思路

維護連續區間：跟蹤當前連續的右邊界 currentMax，表示當前可以連續移除的最大值。
全局最大值：維護 globalMax 記錄所有已添加元素的最大值。
調整條件：當需要移除的元素 expected 超過 currentMax 時，必須調整隊列，調整次數加一，并將 currentMax 更新為 globalMax。

代碼實現

const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false
});let n;
let expected = 1;
let currentMax = 0;
let globalMax = 0;
let adjusts = 0;
let lineCount = 0;rl.on('line', (line) => {if (lineCount === 0) {n = parseInt(line.trim());} else {const trimmedLine = line.trim();if (trimmedLine.startsWith('remove')) {if (expected > currentMax) {adjusts++;currentMax = globalMax;}expected++;} else {const x = parseInt(trimmedLine.split(' ')[2], 10);globalMax = Math.max(globalMax, x);if (x === currentMax + 1) {currentMax = x;}}}lineCount++;if (lineCount === 2 * n + 1) {console.log(adjusts);rl.close();}
});

代碼詳細解析

輸入處理：使用 readline 逐行讀取輸入，第一行為 n。
變量初始化：
- expected：下一個需要移除的元素，初始為1。
- currentMax：當前可連續移除的最大值，初始為0。
- globalMax：所有已添加元素的最大值，初始為0。
- adjusts：調整次數計數器。
處理指令：
- 移除指令：若 expected > currentMax，調整次數加一，currentMax 設為 globalMax。
- 添加指令：更新 globalMax，若元素是 currentMax + 1，擴展 currentMax。
輸出結果：在所有指令處理完畢后輸出調整次數。

示例測試

示例輸入：

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

輸出：

解析：

前三次操作后，currentMax=2，expected=2。
添加3、4、5后，currentMax=5。
第四次移除時，expected=2 不超過 currentMax，無需調整。
最后一次移除時，expected=5 超過 currentMax，調整次數加一。

另一個測試用例：

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

輸出：

解析：

首次移除時，expected=1 > currentMax=0，調整一次。
第二次移除時，expected=2 > currentMax=3，調整第二次。

綜合分析

時間復雜度：O(n)，每個指令處理時間為O(1)。
空間復雜度：O(1)，僅維護幾個變量。
優勢：無需模擬隊列操作，通過維護連續區間和全局最大值高效判斷調整條件。
適用場景：適用于大規模數據，時間復雜度為線性，滿足題目約束。

C++

問題分析

我們需要處理一個特異性的雙端隊列，隊列只能從頭部或尾部添加元素，但移除只能從頭部。目標是按順序移除1到n的元素，計算最小調整次數。調整指的是重新排列隊列，使頭部元素為當前期望值。

解題思路

維護連續區間：跟蹤當前可以連續移除的最大值 current_max，所有已添加元素的最大值 global_max。
添加操作：若添加元素等于 current_max + 1，則擴展連續區間；否則更新 global_max。
移除操作：若期望值超過 current_max，則調整隊列，將 current_max 設為 global_max，調整次數加一。

代碼實現

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;int main() {int n;cin >> n;cin.ignore(); // 忽略換行符int expected = 1; // 期望移除的下一個元素int current_max = 0; // 當前連續區間的最大值int global_max = 0; // 所有已添加元素的最大值int adjusts = 0; // 調整次數string line;for (int i = 0; i < 2 * n; ++i) {getline(cin, line);if (line.substr(0, 6) == "remove") {// 移除操作if (expected > current_max) {adjusts++;current_max = global_max;}expected++;} else {// 解析添加的值istringstream iss(line);string part, op;int x;iss >> part >> op >> x;// 更新全局最大值global_max = max(global_max, x);// 若元素是當前連續區間的下一個值，擴展區間if (x == current_max + 1) {current_max = x;}}}cout << adjusts << endl;return 0;
}

代碼詳細解析

輸入處理：讀取n并忽略換行符。
初始化變量：
- expected：下一個期望移除的元素，初始為1。
- current_max：當前連續區間的最大值，初始為0。
- global_max：所有已添加元素的最大值，初始為0。
- adjusts：調整次數計數器。
處理每條指令：
- 移除指令：若期望值超過 current_max，調整次數加一，current_max 更新為 global_max。
- 添加指令：更新 global_max，若元素是 current_max + 1，則擴展連續區間。
輸出結果：最終打印調整次數。

示例測試

示例輸入：

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

輸出：

解析：

添加1和2后，current_max=2。
第一次移除后，expected=2。
添加3、4、5后，current_max=5。
后續移除無需調整，僅在第4步移除時調整一次。

另一個測試用例：

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

輸出：

解析：

首次移除3時需調整（期望1）。
移除1后，期望2超過 current_max=1，再次調整。

綜合分析

時間復雜度：O(n)，每個指令處理時間為O(1)。
空間復雜度：O(1)，僅維護幾個變量。
優勢：無需模擬隊列操作，通過維護連續區間和全局最大值高效判斷調整條件。
適用性：適用于大規模數據，時間復雜度為線性，滿足題目約束。

C語言

問題分析

解題思路

維護連續區間：跟蹤當前可以連續移除的最大值 current_max，所有已添加元素的最大值 global_max。
添加操作：若添加元素等于 current_max + 1，則擴展連續區間；否則更新 global_max。
移除操作：若期望值超過 current_max，則調整隊列，將 current_max 設為 global_max，調整次數加一。

代碼實現

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define MAX_LINE_LENGTH 20 // 每行指令最大長度int main() {int n;scanf("%d", &n);getchar(); // 讀取換行符int expected = 1;   // 期望移除的下一個元素int current_max = 0; // 當前連續區間的最大值int global_max = 0;  // 所有已添加元素的最大值int adjusts = 0;     // 調整次數計數器char line[MAX_LINE_LENGTH];for (int i = 0; i < 2 * n; i++) {fgets(line, MAX_LINE_LENGTH, stdin);line[strcspn(line, "\n")] = '\0'; // 去除換行符if (strcmp(line, "remove") == 0) { // 移除指令if (expected > current_max) {  // 需要調整adjusts++;current_max = global_max;}expected++;} else { // 添加指令（head add x 或 tail add x）int x;sscanf(line + 8, "%d", &x); // 跳過"head add "或"tail add "// 更新全局最大值if (x > global_max) global_max = x;// 檢查是否擴展連續區間if (x == current_max + 1) {current_max = x;}}}printf("%d\n", adjusts);return 0;
}

代碼詳細解析

輸入讀取：
```
scanf("%d", &n);
getchar(); // 處理輸入n后的換行符
```
- 讀取n后，必須用getchar()清除輸入緩沖區中的換行符，避免影響后續fgets讀取。

變量初始化：

int expected = 1;     // 下一個期望移除的元素（初始為1）
int current_max = 0;  // 當前連續區間的最大值（初始為0）
int global_max = 0;   // 全局最大值（初始為0）
int adjusts = 0;      // 調整次數計數器

處理每條指令：
```
fgets(line, MAX_LINE_LENGTH, stdin);
line[strcspn(line, "\n")] = '\0'; // 去除末尾換行符
```
- fgets讀取整行指令，包括換行符，通過strcspn找到換行符位置并替換為終止符。

移除指令處理：

if (strcmp(line, "remove") == 0) {if (expected > current_max) { // 需要調整adjusts++;current_max = global_max;}expected++;
}

當期望值expected超過current_max時，必須調整隊列，更新current_max為global_max，并增加調整次數。

添加指令處理：
```
sscanf(line + 8, "%d", &x); // 跳過指令前綴（head add 或 tail add）
if (x > global_max) global_max = x;
if (x == current_max + 1) {current_max = x;
}
```
- 從指令字符串的第8個字符開始解析數值（跳過head add 或tail add 共8字符）。
- 更新全局最大值global_max。
- 若元素是current_max + 1，則擴展連續區間。

示例測試

示例輸入：

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

輸出：

解析：

添加1和2后，current_max=2。
第一次remove時，expected=1 <= current_max=2，無需調整。
添加3、4、5后，current_max保持2（因為3不是連續的）。
后續remove操作中，當expected=3 > current_max=2，觸發調整，adjusts=1，current_max=5。
后續操作無需調整，最終總調整次數為1。

另一個測試用例：

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

輸出：

解析：

第一次remove時，expected=1 > current_max=0，調整次數+1，current_max=3。
第二次remove時，expected=2 > current_max=3，調整次數+1，current_max=3。
總調整次數為2。

綜合分析

時間復雜度：O(n)
- 每條指令處理時間為O(1)，總共有2n條指令，時間復雜度為O(n)。
空間復雜度：O(1)
- 僅使用固定數量的變量，不隨輸入規模增長。
優勢：
- 無需模擬隊列：通過維護current_max和global_max，避免了實際隊列操作的復雜度。
- 高效判斷調整條件：直接通過數值比較確定是否需要調整，時間復雜度為O(1)。
適用場景：
- 輸入規模大（n ≤ 3×10?）時，依然保持高效。
- 適用于需要快速判斷調整條件的場景，如實時系統或高頻交易。

GO

問題分析

解題思路

維護連續區間：跟蹤當前可以連續移除的最大值 currentMax，所有已添加元素的最大值 globalMax。
添加操作：若添加元素等于 currentMax + 1，則擴展連續區間；否則更新 globalMax。
移除操作：若期望值超過 currentMax，則調整隊列，將 currentMax 設為 globalMax，調整次數加一。

代碼實現

package mainimport ("bufio""fmt""os""strconv""strings"
)func main() {scanner := bufio.NewScanner(os.Stdin)// 讀取nscanner.Scan()n, _ := strconv.Atoi(scanner.Text())expected := 1       // 期望的下一個移除元素（初始為1）currentMax := 0    // 當前連續區間的最大值globalMax := 0     // 所有已添加元素的最大值adjusts := 0       // 調整次數計數器// 處理2n條指令for i := 0; i < 2*n; i++ {scanner.Scan()line := scanner.Text()if line == "remove" {// 移除操作：檢查是否需要調整if expected > currentMax {adjusts++currentMax = globalMax}expected++} else {// 解析添加操作中的數值（格式：head add x 或 tail add x）parts := strings.Split(line, " ")x, _ := strconv.Atoi(parts[2])// 更新全局最大值if x > globalMax {globalMax = x}// 若元素是連續區間的下一個值，擴展區間if x == currentMax + 1 {currentMax = x}}}fmt.Println(adjusts)
}

代碼詳細解析

輸入處理：
- 使用 bufio.Scanner 逐行讀取輸入，第一行為 n。
- 初始化關鍵變量：
  - expected：下一個期望移除的元素，初始為1。
  - currentMax：當前連續區間的最大值，初始為0。
  - globalMax：所有已添加元素的最大值，初始為0。
  - adjusts：調整次數計數器。

處理指令：

for i := 0; i < 2*n; i++ {scanner.Scan()line := scanner.Text()

循環讀取每條指令（共 2n 條）。

移除操作：
```
if line == "remove" {if expected > currentMax {adjusts++currentMax = globalMax}expected++
}
```
- 當需要移除的 expected 超過 currentMax 時，必須調整隊列。
- 調整次數加一，并將 currentMax 設為 globalMax。
- expected 遞增，準備處理下一個元素。
添加操作：
```
parts := strings.Split(line, " ")
x, _ := strconv.Atoi(parts[2])if x > globalMax {globalMax = x
}if x == currentMax + 1 {currentMax = x
}
```
- 解析添加操作中的數值（如 head add 1 中的 1）。
- 更新 globalMax 為所有已添加元素的最大值。
- 若當前元素是 currentMax + 1，則擴展連續區間。

示例測試

示例輸入：

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

輸出：

解析：

添加1和2后，currentMax=2。
第一次移除時，expected=1 <= currentMax=2，無需調整。
添加3、4、5時，globalMax=5，但 currentMax 保持2（因為3不連續）。
當移除 expected=3 時，觸發調整，adjusts=1，currentMax=5。
后續移除操作無需調整。

另一個測試用例：

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

輸出：

解析：

添加3和1后，globalMax=3，但 currentMax=0（元素不連續）。
第一次移除時，expected=1 > currentMax=0，調整次數+1，currentMax=3。
第二次移除時，expected=2 > currentMax=3，調整次數+1。
總調整次數為2。

綜合分析

時間復雜度：O(n)
- 每條指令處理時間為O(1)，總共有2n條指令，時間復雜度為O(n)。
空間復雜度：O(1)
- 僅使用固定數量的變量，不隨輸入規模增長。
優勢：
- 無需模擬隊列：通過維護 currentMax 和 globalMax，避免了實際隊列操作的復雜度。
- 高效判斷調整條件：直接通過數值比較確定是否需要調整，時間復雜度為O(1)。
適用場景：
- 輸入規模大（n ≤ 3×10?）時，依然保持高效。
- 適用于需要快速判斷調整條件的場景，如實時系統或高頻交易。