跳至主要內容

2025A-特异性双端队列

题目描述与示例

题目描述

有一个特异性的双端队列，该队列可以从头部或尾部添加数据，但是只能从头部移出数据。

小A依次执行2n个指令往队列中添加数据和移出数据。其中n个指令是添加数据（可能从头部添加、也可能从尾部添加），依次添加1到n；n个指令是移出数据。

现在要求移除数据的顺序为1到n。

为了满足最后输出的要求，小A可以在任何时候调整队列中数据的顺序。

请问 小A 最少需要调整几次才能够满足移除数据的顺序正好是1到n。

题目练习网址：https://www.algomooc.com/problem/P2490

输入描述

第一行一个数据n，表示数据的范围。

接下来的2n行，其中有n行为添加数据，指令为：

  • head add x表示从头部添加数据 x，
  • tail add x 表示从尾部添加数据 x，

另外 n 行为移出数据指令，指令为：remove 的形式，表示移出1个数据；

1 ≤ n ≤ 3 * 10^5。

所有的数据均合法。

输出描述

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

示例

输入

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

输出

1

解题思路

这道题乍一看好像需要使用队列进行模拟，但是实际上并不需要。

题意理解

首先需要理解题目含义。以题目提供的唯一示例为例，构建一个空的双端队列，我们模拟这整个过程

指令顺序指令内容队列情况
1head add 1queue = [1]
2tail add 2queue = [1,2]
3remove删除头部元素1，顺序符合要求，因此不需要调整顺序，删除后queue=[2]
4head add 3queue = [3,2]
5tail add 4queue = [3,2,4]
6head add 5queue = [5,3,2,4]
7remove此时队列头部需要删除的元素应该是2，但实际是5，因此需要调整顺序，将queue直接调整顺序为，queue=[2,3,4,5]，然后再删除头部元素2，queue = [3,4,5]
8remove删除头部元素3
9remove删除头部元素4
10remove删除头部元素5

本题重点就在于对**“调整”一词的理解。可以看到，这里的调整并不是指单个元素的位置修改或者和两两元素之间的交换，而是指对整个双端队列进行顺序打乱**。

如果“调整”的含义是其他理解的话，上述例子并不能得到1这个结果。感兴趣的同学可以自己思考一下。

无需基于队列的模拟

容易发现，由于题目要求删除顺序是从1到n，每一次出现remove指令的时候，我们必然要思考当前队头元素是否恰好是当前顺序里面将要被删除的元素。

而一旦需要进行调整，我们一定是贪心地将整个队列都调整成从队头到队尾的顺序结构，这样才可以在连续出现remove指令的时候，不需要额外的顺序调整，也可以按照顺序继续删除。

那么什么时候，我们队列中已经调整好的顺序会被打乱？

我们进行分类讨论

  • 当我们的队列为空的时候，当前加入的元素，无论是从队头加入还是队尾加入，都会使得队列只存在一个元素，不会影响队列中的顺序。
  • 当我们对一个已经调整好的队列，在队尾加入元素时，由于添加的元素总是按照大小顺序添加，因此在队尾添加也不会影响队列中的顺序。
  • 当我们对一个已经调整好的队列，在队头加入元素时，由于添加的元素总是按照大小顺序添加，因此在队头添加的这个元素会使得队列中的顺序发生改变，下次出现remove指令的时候，我们必须再次进行顺序调整。
  • 当我们对一个已经是乱序需要调整的队列，无论从队头还是队尾加入元素，此时队列仍然是乱序，下次遇到remove指令的时候，我们都必须再次进行顺序调整。

所以本题完全不需要使用一个真正的队列进行模拟，而只需要通过题目所给的指令顺序即可判断调整次数。

我们可以设置一个布尔类型变量needModify，当其为True且遇到remove指令的时候，就需要对队列进行调整，调整次数+1。故和调整次数更新相关的代码为

# 初始化调整次数为num
num = 0
# 设置布尔类型变量needModify，表示需要是否需要调整
needModify = False

# 循环2n次，输入2n条指令
for _ in range(2*n):
    # 输入字符串指令
    op = input()
    # 如果指令是remove，且同时此时队列需要调整
    if op == "remove":
        if needModify:
            # 调整次数加1，且重置needModify变量为False
            num += 1
            needModify = False

于此同时，当队列不为空且指令为在队头添加元素时，我们需要将needModify修改为False。

当remove指令出现的次数removeNum（表示一共移除了removeNum个元素）加1后恰好等于下一个添加的元素数值时，此时队头为空。故可以修改代码如下

# 初始化调整次数为num
num = 0
# 设置布尔类型变量needModify，表示需要是否需要调整
needModify = False
# 设置removeNum表示删除操作出现了多少次
removeNum = 0

# 循环2n次，输入2n条指令
for _ in range(2*n):
    # 输入字符串指令
    op = input()
    # 如果指令是remove，且同时此时队列需要调整
    if op == "remove":
        if needModify:
            # 调整次数加1，且充值needModify变量为False
            num += 1
            needModify = False
        # 删除操作次数加1
        removeNum += 1
    # 如果指令是从队头添加元素
    # 且此时队列不为空
    # 不为空的条件为：当前删除次数+1后，不等于此时即将添加的元素数值
    # 由于关于从队头添加元素的指令一定为"head add X"
    # 所以直接利用切片，从索引9之后往后取，就可以获得完整的数字
    # 此处也可以使用op.split()[2]来获得
    if op[0] == "h" and int(op[9:]) != removeNum + 1:
        # 那么队列需要调整，修改needModify为True
        needModify = True

而其他的情况都不用修改任何变量，直接不予讨论即可。至此代码就完成了。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 输入元素个数n
n = int(input())
# 初始化调整次数为num
num = 0
# 设置布尔类型变量needModify，表示需要是否需要调整
needModify = False
# 设置removeNum表示删除操作出现了多少次
removeNum = 0

# 循环2n次，输入2n条指令
for _ in range(2*n):
    # 输入字符串指令
    op = input()
    # 如果指令是remove，且同时此时队列需要调整
    if op == "remove":
        if needModify:
            # 调整次数加1，且充值needModify变量为False
            num += 1
            needModify = False
        # 删除操作次数加1
        removeNum += 1
    # 如果指令是从队头添加元素
    # 且此时队列不为空
    # 不为空的条件为：当前删除次数+1后，不等于此时即将添加的元素数值
    # 由于关于从队头添加元素的指令一定为"head add X"
    # 所以直接利用切片，从索引9之后往后取，就可以获得完整的数字
    # 此处也可以使用op.split()[2]来获得
    if op[0] == "h" and int(op[9:]) != removeNum + 1:
        # 那么队列需要调整，修改needModify为True
        needModify = True


# 输出最终调整次数
print(num)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入元素个数 n
        int n = scanner.nextInt();
        scanner.nextLine(); // 读取换行符，防止影响后续输入

        // 初始化调整次数 num
        int num = 0;
        // 设置布尔类型变量 needModify，表示是否需要调整
        boolean needModify = false;
        // 设置 removeNum 记录删除操作出现的次数
        int removeNum = 0;

        // 循环 2n 次，输入 2n 条指令
        for (int i = 0; i < 2 * n; i++) {
            // 读取指令
            String op = scanner.nextLine();

            // 如果指令是 remove，且此时队列需要调整
            if (op.equals("remove")) {
                if (needModify) {
                    num++; // 调整次数加 1
                    needModify = false; // 重置 needModify
                }
                removeNum++; // 删除操作次数加 1
            }
            // 处理 "head add X" 指令
            else if (op.startsWith("head add ")) {
                // 提取 X 的值（去除 "head add " 后的部分）
                int value = Integer.parseInt(op.substring(9));

                // 如果当前删除次数 + 1 不等于即将添加的元素数值
                if (value != removeNum + 1) {
                    needModify = true; // 需要调整
                }
            }
        }

        // 输出最终调整次数
        System.out.println(num);

        scanner.close();
    }
}

C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    
    // 输入元素个数 n
    cin >> n;
    cin.ignore(); // 读取换行符，防止影响后续输入

    // 初始化调整次数 num
    int num = 0;
    // 设置布尔类型变量 needModify，表示是否需要调整
    bool needModify = false;
    // 设置 removeNum 记录删除操作出现的次数
    int removeNum = 0;

    // 循环 2n 次，输入 2n 条指令
    for (int i = 0; i < 2 * n; i++) {
        string op;
        getline(cin, op);

        // 如果指令是 remove，且此时队列需要调整
        if (op == "remove") {
            if (needModify) {
                num++; // 调整次数加 1
                needModify = false; // 重置 needModify
            }
            removeNum++; // 删除操作次数加 1
        }
        // 处理 "head add X" 指令
        else if (op.substr(0, 9) == "head add ") {
            // 提取 X 的值（去除 "head add " 后的部分）
            int value = stoi(op.substr(9));

            // 如果当前删除次数 + 1 不等于即将添加的元素数值
            if (value != removeNum + 1) {
                needModify = true; // 需要调整
            }
        }
    }

    // 输出最终调整次数
    cout << num << endl;

    return 0;
}

C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    int n;
    
    // 输入元素个数 n
    scanf("%d", &n);
    getchar(); // 读取换行符，防止影响后续输入

    // 初始化调整次数 num
    int num = 0;
    // 设置布尔类型变量 needModify，表示是否需要调整
    int needModify = 0;
    // 设置 removeNum 记录删除操作出现的次数
    int removeNum = 0;

    // 循环 2n 次，输入 2n 条指令
    for (int i = 0; i < 2 * n; i++) {
        char op[20]; // 存储指令，最多 20 个字符，防止溢出
        fgets(op, sizeof(op), stdin);
        
        // 移除换行符
        op[strcspn(op, "\n")] = '\0';

        // 如果指令是 remove，且此时队列需要调整
        if (strcmp(op, "remove") == 0) {
            if (needModify) {
                // 调整次数加 1，并重置 needModify 变量为 false
                num++;
                needModify = 0;
            }
            // 删除操作次数加 1
            removeNum++;
        }
        // 如果指令是从队头添加元素（"head add X"）
        else if (strncmp(op, "head add ", 9) == 0) {
            // 获取指令末尾的数字 X
            int value = atoi(op + 9); // "head add X" -> 提取 X 作为整数

            // 如果当前删除次数 + 1 不等于即将添加的元素数值
            if (value != removeNum + 1) {
                // 那么队列需要调整，修改 needModify 为 true
                needModify = 1;
            }
        }
    }

    // 输出最终调整次数
    printf("%d\n", num);

    return 0;
}

Node JavaScript

const readline = require("readline");

// 创建输入读取接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n = 0; // 任务数量
let num = 0; // 需要调整的次数
let needModify = false; // 记录是否需要调整
let removeNum = 0; // 记录 remove 操作的次数
let lineCount = 0; // 记录读取的行数

rl.on("line", (line) => {
    if (lineCount === 0) {
        // 读取元素个数 n
        n = parseInt(line);
    } else {
        // 处理指令
        if (line === "remove") {
            if (needModify) {
                num++;
                needModify = false;
            }
            removeNum++;
        } else if (line.startsWith("head add ")) {
            // 解析 "head add X"，获取 X 数值
            let value = parseInt(line.split(" ")[2]);

            // 判断是否需要调整
            if (value !== removeNum + 1) {
                needModify = true;
            }
        }
    }
    lineCount++;

    // 读取完所有 2n 条指令后，输出结果并关闭输入流
    if (lineCount > 2 * n) {
        console.log(num);
        rl.close();
    }
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

func main() {
        // 读取标准输入
        scanner := bufio.NewScanner(os.Stdin)

        // 读取元素个数 n
        scanner.Scan()
        n, _ := strconv.Atoi(scanner.Text())

        // 初始化变量
        num := 0         // 需要调整的次数
        needModify := false // 记录是否需要调整
        removeNum := 0   // 记录 remove 操作的次数

        // 读取 2n 条指令
        for i := 0; i < 2*n; i++ {
                scanner.Scan()
                op := scanner.Text()

                // 处理 "remove" 操作
                if op == "remove" {
                        if needModify {
                                num++
                                needModify = false
                        }
                        removeNum++
                } else if strings.HasPrefix(op, "head add ") {
                        // 解析 "head add X"，获取 X 数值
                        parts := strings.Split(op, " ")
                        value, _ := strconv.Atoi(parts[2])

                        // 判断是否需要调整
                        if value != removeNum+1 {
                                needModify = true
                        }
                }
        }

        // 输出最终调整次数
        fmt.Println(num)
}

时空复杂度

时间复杂度：O(N)。需要循环2*N，处理输入的2*N行指令。

空间复杂度：O(1)。除了输入的序列，仅需若干常数变量维护遍历过程。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法