LeetCode 2102 序列顺序查询题解用平衡二叉树与固定堆技巧实现动态“第 k 好”景点查询【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文围绕力扣第 2102 题「序列顺序查询」SORTracker展开完整讲解其题目定义、排序规则的隐藏“坑”、基于平衡二叉树SortedList的推荐解法以及基于固定堆技巧的替代思路。阅读本文后你将掌握“动态插入 按序取第 k 优”这一类数据流问题在 Python 中的落地写法并能将其迁移到数据流中位数、第 K 大元素等同构场景。全文以仓库中 problems/2102.sequentially-ordinal-rank-tracker.md 的题解为主体骨架并结合仓库的堆专题与二分专题做源码级佐证。题目背景动态排行榜的“第 k 好”查询这道题要搭建一个“观光景点排行榜”系统。系统初始为空需要支持两类操作添加景点每次加入一个景点景点由唯一的名称name和整数评分score组成查询景点第i次调用查询接口时返回当前所有已添加景点中第i好的景点名称。“更好”的定义有两条明确规则评分越高越好score越大排名越靠前评分相同时字典序较小的name更好。换句话说排行榜始终按“评分降序、同分时名称字典序升序”排列查询接口按调用次序依次取出第 1、第 2、第 3……好的景点。题目保证在任意查询时刻查询次数都不超过系统中景点的数目因此查询下标不会越界。接口设计与数据规模需要实现的类签名如下SORTracker() 初始化系统 void add(string name, int score) 添加一个名为 name、评分为 score 的景点 string get() 返回第 i 好的景点其中 i 是目前系统查询的次数包括当前这次查询题目给出的约束条件摘自 problems/2102.sequentially-ordinal-rank-tracker.mdname只包含小写英文字母且每个景点名字互不相同1 name.length 101 score 105任意时刻调用get的次数都不超过调用add的次数总共调用add和get不超过4 * 10^4。最后一条约束至关重要总操作量在4 * 10^4量级意味着单次操作做到O(log n)或更优是完全可行的而每次查询前都对全部景点排序的O(n log n)写法大概率无法通过。示例逐步推演以题目给出的输入为例输入 [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]逐步解释如下操作当前排行榜好 → 坏说明add(bradford, 2)bradford初始只有一个景点add(branford, 3)branford, bradfordbranford 评分 3 2排前面get()第 1 次—返回最好景点branfordadd(alps, 2)branford, alps, bradfordalps 与 bradford 同分 2但 alps 字典序小于 bradford因此 alps 更好get()第 2 次—返回第 2 好景点alpsadd(orland, 2)branford, alps, bradford, orlandorland 同分 2 但字典序更大排最后get()第 3 次—返回bradfordadd(orlando, 3)branford, orlando, alps, bradford, orlandorlando 评分 3插入到 branford 之后get()第 4 次—返回bradfordadd(alpine, 2)branford, orlando, alpine, alps, bradford, orlandalpine 与 alps 同分字典序更小插入到 alps 之前get()第 5 次—返回bradfordget()第 6 次—返回orland从推演可以直观看到查询次数就是排名下标每一次get()取的是当前全量有序集合中固定位置上的元素且该位置会随调用次数递增。前置知识平衡二叉树与 SortedList题解明确把平衡二叉树列为核心前置知识。为什么它合适因为我们需要维护一个“始终有序、支持动态插入、支持按下标取元素”的集合插入元素后集合自动保持有序能够以O(log n)的代价定位第 k 个元素。仓库的二分专题 thinkings/binary-search-2.md 在讲解前缀和有序化技巧时也给出了同样的结论使用平衡二叉树代替数组可使得插入的时间复杂度降低到O(log n)并指出“Python 可使用SortedList来实现Java 可用TreeMap代替”。这与本题“动态插入 有序取第 k 个”的需求完全同构。Python 中sortedcontainers库提供的SortedList正是这样一个容器add()插入后自动保持有序sl[i]支持按下标随机访问天然适配本题。思路推演为什么想到了平衡二叉树和固定堆本题属于典型的“动态求第 k 优”问题。题解给出了两条思考路径路径一平衡二叉树推荐。维护一个始终有序的容器查询时直接按下标取第 i 个即可。容器内部的有序性由平衡树保证插入与查询都只花费对数时间。如果对平衡二叉树不熟悉可以参考仓库二分专题 thinkings/binary-search-2.md 中对有序容器应用的讲解。路径二固定堆技巧。动态求极值的问题通常可以借助堆解决但本题求的是第 k 大而非最大普通堆只能给出堆顶这一个极值。此时需要用“固定堆”技巧。仓库堆专题 thinkings/heap-2.md 的“技巧一 - 固定堆”给出了核心口诀固定一个大小为 k 的大顶堆可以快速求第 k 小的数反之固定一个大小为 k 的小顶堆可以快速求第 k 大的数。代码上通过“每 pop 出去一个就 push 进来一个”来维持堆的大小不大于 k。套用到本题维护一个大小恰为当前查询次数 i 的小顶堆堆中始终保存“当前第 i 好以内的景点”堆顶即为第 i 好的景点。由于每次get()后 i 递增堆大小同步调整即可。这一思路与仓库中另一道经典题 problems/215.kth-largest-element-in-an-array.md 的“维护大小为 K 的小顶堆求第 K 大”解法一脉相承而“动态数据流 按序取中位数/第 k 值”的整体框架则可以参考 problems/295.find-median-from-data-stream.md 中“两个堆”的配合方式。仓库堆专题 thinkings/heap.md 也在“三个技巧”预告中把“固定堆”列为堆解题法的核心技巧之一。排序规则里的“坑”同分时字典序的处理确定用平衡二叉树SortedList后第一步自然是把(score, name)二元组整体存入容器Python 元组会先按score再按name排序。但直接这样做是不对的。先看第一版“看似正确”的写法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这段代码用self.i从-1开始即从有序集合的末尾往前取取到的是“评分最高”的景点。问题在于同分时的表现(score, name)升序排列时同分的多个景点中字典序较大的 name 排得更靠后因此从末尾取出的反而是字典序较大的那个——这恰好违背了题目“同分时字典序较小的景点更好”的约定。从错误到正确三种写法的演进错误写法一直接存(score, name)。如上所述升序排列 从尾部取会在同分时返回字典序较大的景点违背题意。错误写法二把 name 转数字后取反。一种直观的修正思路是既然字典序小的更好就把 name 转换后的数值取反存入让“更好的”在排序时更靠前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其中toNumber(name)需要自行实现字符串到数字的映射如按位加权转换。这种写法能通过但实现繁琐字符串不能直接取反必须先做一次转换还要额外承担转换开销。正确写法对 score 取反。题解给出了一个更简洁的等价做法——在add时对score取反get时从另一头取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()为什么这样是对的存储元组变为(-score, name)后SortedList的升序排列等价于先按-score升序即评分降序——评分越高排得越靠前同分时-score相同再按name升序——字典序越小排得越靠前。于是有序集合的第0个元素恰好是“第 1 好”的景点第i个元素就是“第i1好”的景点。相应地self.i从0开始每次get()后自增正好与题目“第 i 次查询返回第 i 好”的定义对齐。关键点题解反复强调的核心关键点只有一个add的时候对score取反即可一举达成“如果有两个景点的评分一样那么字典序较小的景点更好”的效果。这个技巧的本质是把排序方向折叠进存储键不改变容器的升序语义只改变键的构造方式从而让“更优”的元素天然落在更小的下标上。它比“给 name 做数字转换取反”更轻量、更不易出错是本题最值得记忆的套路。复杂度分析按题解给出的分析令 n 为景点总数时间复杂度O(log n)。SortedList的插入add与按下标访问get均基于有序树/有序序列模型单次操作开销为对数级别总操作量不超过4 * 10^4整体O(n log n)完全在可接受范围内。空间复杂度O(n)。需要存储全部已添加景点的键值对。补充说明上述复杂度基于“平衡二叉树模型”的理论代价。sortedcontainers的SortedList在 Python 中实际基于分块有序列表实现具体常数与实现细节可参阅该库文档若希望严格获得平衡树语义也可像 thinkings/binary-search-2.md 中建议的那样在 Java 中使用TreeMap等原生有序结构替代。同类问题延伸动态第 k 家族掌握了本题的“有序容器 按序取第 k 个”框架后可以顺势打通仓库中一批同构问题problems/215.kth-largest-element-in-an-array.md静态数组中求第 K 大元素用“固定大小为 K 的小顶堆”即可对应本题思路中的固定堆路线problems/295.find-median-from-data-stream.md动态数据流中求中位数本质是“动态取第 n/2 个”用两个堆大顶堆 小顶堆维持前后两半与本题“维护前 i 优”的框架一脉相承二分专题 thinkings/binary-search-2.md 中的有序容器应用在需要“插入保持有序 快速定位”的场景如区间和计数中复用SortedList或TreeMap。小结LeetCode 2102「序列顺序查询」是一道典型的动态有序集合 按序取第 k 值问题。解题主线是用平衡二叉树Python 的SortedList维护全量景点的有序排列查询时按下标直接取数难点不在数据结构本身而在排序规则的细节处理——通过对score取反把“评分降序 同分字典序升序”的双重比较规则折叠进存储键从而用一行代码化解了看似棘手的“坑”。这一“取反折叠排序方向”的技巧与“固定堆求第 k 大”的思路可一并迁移到数据流中位数、第 K 大元素等仓库中记录的大量同类题目上。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考