题目链接

字符串优先队列

题目描述

你需要维护一个字符串序列（多重集合），支持以下三种操作：

  1. 插入: 1 s，将字符串 s 加入序列。
  2. 查询: 2，输出序列中字典序最小的字符串。
  3. 删除: 3，删除序列中字典序最小的字符串（若有多个，只删除一个）。

这是一个主函数模式的题目，你需要使用官方提供的模板来填充函数。

输入格式:

  • 第一行是一个整数 ，表示操作的总数。
  • 接下来 行，每行描述一个操作。

输出格式:

  • 对于每个查询操作（类型 2），输出一行，为当前序列中字典序最小的字符串。

示例: 输入:

5
1 abc
1 cda
2
3
2

输出:

abc
cda

解题思路

这个问题要求我们动态地维护一个集合，并能高效地进行插入、查询字典序最小值和删除字典序最小值。这和我们之前处理整数优先队列的逻辑完全相同，只是操作的对象从整数变为了字符串。

最小优先队列 (Min-Priority Queue) 依然是解决此问题的最佳数据结构。幸运的是，所有主流语言的标准库都为字符串提供了默认的字典序比较，这意味着我们可以直接将字符串放入优先队列，而不需要像上一题那样编写复杂的自定义比较器。

各语言实现

  • C++: std::priority_queue 默认是最大堆。为了找到字典序最小的字符串，我们需要一个最小堆。可以通过向模板提供 std::greater<string> 比较器来实现。题目模板已经为我们设置好了 priority_queue<string, vector<string>, greater<string>> s;。
  • Java: java.util.PriorityQueue 对字符串默认就是按字典序升序排列的最小堆，因为 String 类实现了 Comparable 接口。题目模板提供的 new PriorityQueue<>()可以直接使用。
  • Python: heapq 模块在列表上实现一个最小堆。字符串在 Python 中默认按字典序比较，所以直接将字符串推入列表即可。

算法步骤:

  1. 根据题目模板，在 insertValue, deleteValue, getTop 函数中封装对全局优先队列的相应操作。
    • insertValue(x): 将字符串 x 推入堆。
    • deleteValue(): 弹出堆顶元素。
    • getTop(): 返回堆顶元素。
  2. 在执行 delete 和 get 操作前，需要判断队列是否为空。
  3. 主函数逻辑由模板提供，它会调用我们填充的函数来完成任务。

代码

#include<bits/stdc++.h>
using namespace std;

// 使用 greater<string> 将默认的最大堆转为最小堆
priority_queue<string, vector<string>, greater<string>> s;

void insertValue(string x){
    s.push(x);
}

void deleteValue(){
    if (!s.empty()) {
        s.pop();
    }
}

string getTop(){
    if (!s.empty()) {
        return s.top();
    }
    return ""; // Or handle as per problem constraints on empty query
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q,op;
    string x;
    cin>>q;
    while(q--){
        cin>>op;
        if(op==1){
            cin>>x;
            insertValue(x);
        }
        if(op==2){
            cout<<getTop()<<endl;
        }
        if(op==3){
            deleteValue();
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    // String 实现了 Comparable，PriorityQueue 默认就是按字典序的最小堆
    static PriorityQueue<String> s = new PriorityQueue<>();
    
    public static void insertValue(String x) {
        s.add(x);
    }

    public static void deleteValue() {
        if (!s.isEmpty()) {
            s.poll();
        }
    }

    public static String getTop() {
        if (!s.isEmpty()) {
            return s.peek();
        }
        return ""; // Or handle as per problem constraints
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int q = scanner.nextInt();
        while (q-- > 0) {
            int op = scanner.nextInt();
            if (op == 1) {
                String x = scanner.next();
                insertValue(x);
            }
            if (op == 2) {
                System.out.println(getTop());
            }
            if (op == 3) {
                deleteValue();
            }
        }
        scanner.close();
    }
}

import heapq

# heapq 是最小堆，字符串默认按字典序比较
s = []

def insertValue(x):
    heapq.heappush(s, x)

def deleteValue():
    if s:
        heapq.heappop(s)

def getTop():
    if s:
        return s[0]
    return "" # Or handle as per problem constraints

if __name__ == "__main__":
    q = int(input())
    for _ in range(q):
        line = input().split()
        op = int(line[0])
        if op == 1:
            x = line[1]
            insertValue(x)
        elif op == 2:
            print(getTop())
        elif op == 3:
            deleteValue()

算法及复杂度

  • 数据结构: 优先队列（最小堆）
  • 时间复杂度: 对于 次操作，插入和删除的代价是 ，查询是 ，其中 是堆中当前的元素数量， 是字符串的平均长度（因为字符串比较的代价与长度有关）。总时间复杂度大致为 。
  • 空间复杂度: ，即所有插入的字符串的总长度。