# 2102. 序列顺序查询

### 题目地址(2102. 序列顺序查询)

<https://leetcode-cn.com/problems/21/>

### 题目描述

```
一个观光景点由它的名字 name 和景点评分 score 组成，其中 name 是所有观光景点中 唯一 的字符串，score 是一个整数。景点按照最好到最坏排序。景点评分 越高 ，这个景点越好。如果有两个景点的评分一样，那么 字典序较小 的景点更好。

你需要搭建一个系统，查询景点的排名。初始时系统里没有任何景点。这个系统支持：

添加 景点，每次添加 一个 景点。
查询 已经添加景点中第 i 好 的景点，其中 i 是系统目前位置查询的次数（包括当前这一次）。
比方说，如果系统正在进行第 4 次查询，那么需要返回所有已经添加景点中第 4 好的。

注意，测试数据保证 任意查询时刻 ，查询次数都 不超过 系统中景点的数目。

请你实现 SORTracker 类：

SORTracker() 初始化系统。
void add(string name, int score) 向系统中添加一个名为 name 评分为 score 的景点。
string get() 查询第 i 好的景点，其中 i 是目前系统查询的次数（包括当前这次查询）。

 

示例：

输入：
["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]
[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]
输出：
[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

解释：
SORTracker tracker = new SORTracker(); // 初始化系统
tracker.add("bradford", 2); // 添加 name="bradford" 且 score=2 的景点。
tracker.add("branford", 3); // 添加 name="branford" 且 score=3 的景点。
tracker.get();              // 从好带坏的景点为：branford ，bradford 。
                            // 注意到 branford 比 bradford 好，因为它的 评分更高 (3 > 2) 。
                            // 这是第 1 次调用 get() ，所以返回最好的景点："branford" 。
tracker.add("alps", 2);     // 添加 name="alps" 且 score=2 的景点。
tracker.get();              // 从好到坏的景点为：branford, alps, bradford 。
                            // 注意 alps 比 bradford 好，虽然它们评分相同，都为 2 。
                            // 这是因为 "alps" 字典序 比 "bradford" 小。
                            // 返回第 2 好的地点 "alps" ，因为当前为第 2 次调用 get() 。
tracker.add("orland", 2);   // 添加 name="orland" 且 score=2 的景点。
tracker.get();              // 从好到坏的景点为：branford, alps, bradford, orland 。
                            // 返回 "bradford" ，因为当前为第 3 次调用 get() 。
tracker.add("orlando", 3);  // 添加 name="orlando" 且 score=3 的景点。
tracker.get();              // 从好到坏的景点为：branford, orlando, alps, bradford, orland 。
                            // 返回 "bradford".
tracker.add("alpine", 2);   // 添加 name="alpine" 且 score=2 的景点。
tracker.get();              // 从好到坏的景点为：branford, orlando, alpine, alps, bradford, orland 。
                            // 返回 "bradford" 。
tracker.get();              // 从好到坏的景点为：branford, orlando, alpine, alps, bradford, orland 。
                            // 返回 "orland" 。


 

提示：

name 只包含小写英文字母，且每个景点名字互不相同。
1 <= name.length <= 10
1 <= score <= 105
任意时刻，调用 get 的次数都不超过调用 add 的次数。
总共 调用 add 和 get 不超过 4 * 104 
```

### 前置知识

* 平衡二叉树

### 公司

* 暂无

### 思路

这种题目适合使用平衡二叉树来做。如果对其不熟悉，可以参考我的二分专题。

另外这种动态求极值的，也可以考虑使用堆。不过我们求的是 第 k 大，而不是最大。因此可使用堆中的固定堆技巧来实现。具体可以参考我的堆专题。

想到使用平衡二叉树后，思路就简单了。 一开始我的想法是：

```py

from sortedcontainers import SortedList
class SORTracker:

    def __init__(self):
        sl = SortedList()
        self.i = -1
        self.sl = sl

    def add(self, name: str, score: int) -> None:
        self.sl.add((score, name))

    def get(self) -> str:
        ans = self.sl[self.i][1]
        self.i += 1
        return ans
```

不过这是不对的。

这是因为题目约定了**如果有两个景点的评分一样，那么 字典序较小   的景点更好**。

而上面的代码会返回字典序较大的。一种简单的想法是 add 的时候将 name 取反放进去。由于字符串不能直接取反，我们需要先想办法把他们转为数字进行处理。代码如下

```py

from sortedcontainers import SortedList
class SORTracker:

    def __init__(self):
        sl = SortedList()
        self.i = -1
        self.sl = sl

    def add(self, name: str, score: int) -> None:
        self.sl.add((score, -1 * toNumber(name) ,name))

    def get(self) -> str:
        ans = self.sl[self.i][2]
        self.i += 1
        return ans
```

实际上一种更简单的方法是 add 的时候对 score 进行取反，接下来 get 的时候从另外一头取即可。 具体见下方代码。

### 关键点

* add 的时候对 score 取反，达到**如果有两个景点的评分一样，那么 字典序较小   的景点更好**的效果。

### 代码

* 语言支持：Python3

Python3 Code:

```python

from sortedcontainers import SortedList
class SORTracker:

    def __init__(self):
        sl = SortedList()
        self.i = 0
        self.sl = sl

    def add(self, name: str, score: int) -> None:
        self.sl.add((-score, name))

    def get(self) -> str:
        ans = self.sl[self.i][1]
        self.i += 1
        return ans



# Your SORTracker object will be instantiated and called as such:
# obj = SORTracker()
# obj.add(name,score)
# param_2 = obj.get()

```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(logn)$
* 空间复杂度：$O(n)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/uv3eyd.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2102.sequentially-ordinal-rank-tracker.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.