1. 题目到底在问什么不是查询是移动后返回位置1.1 一句话复述题意第一次看到查询带键的排列这个中文翻译我也愣了一下。翻回英文原题Queries on a Permutation With Key题目本身非常朴素给你一个整数 m初始排列是[1, 2, 3, ..., m]再给你一个查询数组queries里面的每个数字一定在 1 到 m 之间。对于每个查询 q你要做两件事第一找到 q 在当前排列中的下标第二把 q 移动到排列开头其他数字的相对顺序保持不变。最后把所有查询得到的下标按顺序返回。这题在 LeetCode 上是 14xx 中段的题目属于那种题目看起来短、样例一看就懂、但真动手写却容易写飞的类型。它不考复杂贪心或者 DP考的是你对顺序维护这个基本操作的敏感度。很多人在热门 100 题清单里刷不到它但它经常作为周赛题的基础组件出现——位置查询、动态排名、把某个 key 提到队首这些场景组合在一起就是这题的核心。1.2 手动走一遍官方样例官方样例是m 5, queries [3, 1, 2, 1]期望输出[2, 1, 2, 1]。我习惯把这个过程画成一张表因为画完你就知道每一轮发生了什么轮次查询值当前排列查到下标移动后排列13[1, 2, 3, 4, 5]2[3, 1, 2, 4, 5]21[3, 1, 2, 4, 5]1[1, 3, 2, 4, 5]32[1, 3, 2, 4, 5]2[2, 1, 3, 4, 5]41[2, 1, 3, 4, 5]1[1, 2, 3, 4, 5]注意第三轮查到 2 的下标是 2因为此时排列是[1, 3, 2, 4, 5]数字 2 前面确实有 1 和 3 两个元素。第四轮查询 1 之前2 已经被提到了前面所以 1 又回到下标 1。这个例子把移动会影响后续查询结果这件事体现得很清楚如果直接把原始排列的下标预处理好不去更新排列结果一定是错的。1.3 容易被样例带偏的下标问题题目要返回的是 0-based 下标也就是说数字前面有几个元素就返回几。如果数字已经在队首返回 0而不是 1。这点蛮多题解容易绕晕尤其是从 C 的 iterator 习惯走过来的朋友很容易把所有答案加 1结果样例全挂。还有一个隐藏条件queries里的数字一定在[1, m]范围内所以不用处理找不到的情况。这让你可以放心用index、find这类直接定位的接口。数据范围我印象里 m 和queries的长度都在 1000 这个量级所以暴力实现也完全能过。但只满足于暴力就浪费了这题最有价值的树状数组思路。2. 第一版暴力做法Python 列表模拟其实已经很能打2.1 最直观的代码如果只求通过Python 列表版本可以写得很短from typing import List def processQueries(queries: List[int], m: int) - List[int]: perm list(range(1, m 1)) ans [] for q in queries: idx perm.index(q) ans.append(idx) perm.pop(idx) perm.insert(0, q) return ansperm.index(q)返回 q 第一次出现的位置因为排列中每个数字只有一个所以这个位置就是它当前的下标。后面两行做的事情是把 q 从原位置摘掉再插到最前面完全对应题目要求的移动。这里不需要自己写循环去找下标list.index是 CPython 里的 C 实现在小数据下反而比自己写 Python 循环快。这个版本在 LeetCode 上确实能过因为 m 最多 1000、queries最多 1000总操作量在百万级别完全不是问题。2.2 复杂度到底怎么算很多博客直接写暴力复杂度 O(n*m)但没说清楚为什么。拆开看perm.index(q)需要从开头扫描到 q最坏情况是扫描 m 个元素。perm.pop(idx)删除某个位置后它后面的所有元素要整体左移一位。perm.insert(0, q)在头部插入原排列里所有元素又要整体右移一位。也就是说一个查询最坏会触发大约两次数组搬移每次搬移长度接近 m。如果queries长度是 n总复杂度就是 O(n*m)额外空间是 O(m)。当 m 和 n 都是 1000 时1000 乘 1000 就是 10^6 量级对计算机来说很轻松。但如果把 m 和 n 同时放大到 10^5暴力要做 10^10 次操作那就彻底不可接受了。后面的树状数组解法就是冲着这个瓶颈去的。2.3 三个容易翻车的细节第一返回值千万别加 1。LeetCode 官方样例明确是 0-based如果你按照第几个元素来理解prefix 逻辑全乱。第二pop之后必须insert(0, q)不能只pop不插回否则排列长度直接少 1。第三同一个数字可能被查询多次比如queries [1, 1, 1]每次都要正常返回 0因为第一次查到它之后它一直在队首。这些细节单独看都很简单但写代码时手一快就容易漏。3. 链表模拟看着高效为什么我最后放弃了3.1 双向链表模型是怎么设计的很多人看到把元素移到队首这个操作第一反应是链表移动节点是 O(1)再也不用像数组那样整体搬移了。理论上可以给每个数字建一个节点再用一个数组node[i]指向值为 i 的节点头节点单独维护。查询时从 head 一路往后走数到目标节点移动时把目标节点从链上摘下来放到 head 前面。这个模型本身没错而且如果你需要反复在任意位置插入删除链表确实比数组稳定。但放在这题里它没有解决真正的问题查询下标仍然需要从头部开始数。链表只是让删除 插入头部变成 O(1)而找到 q 在第几个位置这一步还是 O(m)。3.2 复杂度瓶颈其实没变用链表模拟每次查询平均要沿着 next 指针走 m/2 步复杂度依然是 O(n*m)。和数组版相比链表省掉了元素搬移但代价是每个节点都是独立对象指针跳来跳去CPU 的 cache 非常不友好。在 m 1000 这个数据规模下链表版大概率跑不过 Python 的list.index pop insert。所以我的结论是如果只追求通过题目不要为了显得高级上链表如果是为了准备面试链表也不是最优解因为面试官紧接着会问你还有没有更快的排名方式。真正值得学的是把移动和查询排名分开处理的数据结构。3.3 由链表引出的正确方向链表做不到的是快速知道某个 key 当前排第几。要同时支持两个操作查询一个 key 在当前排列中的排名把这个 key 移动到最前面。这两个操作组合起来本质是动态排名问题。平衡树可以维护子树大小做到 O(log n)但实现成本偏高。如果查询序列是提前给定的可以离线处理用一个更轻量的树状数组在固定槽位上完成这就是下一节要说的核心思路。4. 正餐树状数组 固定槽位把复杂度降到 O((mn)log(mn))4.1 核心思想先留 n 个空槽位不要动态地移动数组元素而是把整个排列看成一个固定长度的槽位带。槽位带的长度设为 mn其中 n 是queries的长度。为什么预留 n 个空位因为每次查询都会把一个数字移动到队首最多执行 n 次移动所以最多需要 n 个新队首位置。初始状态下把[1, 2, ..., m]依次放在最右侧的连续槽位上数字 i 放在ni号槽位。这样左侧从 1 到 n 全是空槽位作为未来的队首预备区。记住一个关键结论槽位编号越小排列越靠前。所以把 q 移动到队首就等价于把 q 放到当前最靠左的空槽位里准确说是放到最靠右的那个可用空槽位然后继续往左收缩。4.2 为什么初始位置要放在 ni而不是 i如果直接把数字 i 放在槽位 i那么第一次移动队首时放到 0 号槽位就会越界。为了不引入负数下标可以整体右移 n 位让初始数组占据[n1, nm]左边留出的[1, n]专门用来安置新队首。这是纯工程上的偏移优化不是算法上的玄学。用树状数组Fenwick Tree记录每个槽位是否被占用。槽位被占用就存 1空着就存 0。查询 q 的位置时只需要求prefix(pos[q])也就是槽位pos[q]左侧包含自己有多少个被占用的槽位。因为 q 本身一定占着一个槽位所以真实下标应该是prefix(pos[q]) - 1。移动 q 时分三步在旧槽位pos[q]上减 1表示这个位置空出来了把 q 放进当前队首空槽front并在这个槽位上加 1更新pos[q] front然后front向左移动一格。front的初始值是 n。第一次移动用槽位 n第二次用 n-1最后一次一般落到槽位 1。整棵 BIT 的下标始终从 1 开始不会碰到 0 号下标这也是留空位的另一个好处。4.3 完整代码与每一步的对应关系from typing import List class Fenwick: def __init__(self, n: int): self.n n self.tree [0] * (n 1) def add(self, i: int, delta: int) - None: while i self.n: self.tree[i] delta i i -i def prefix(self, i: int) - int: s 0 while i 0: s self.tree[i] i - i -i return s def processQueries(queries: List[int], m: int) - List[int]: n len(queries) size m n bit Fenwick(size) pos [0] * (m 1) # 初始排列[1..m] 依次放在 n1 到 nm 号槽位 for value in range(1, m 1): slot n value pos[value] slot bit.add(slot, 1) front n # 第一个新队首会放在第 n 号槽位 ans [] for q in queries: # q 当前 0-based 下标 它前面有多少个被占用的槽位 rank bit.prefix(pos[q]) ans.append(rank - 1) # 从旧槽位移除 q bit.add(pos[q], -1) # 放到当前队首空槽 bit.add(front, 1) pos[q] front # 队首预备区指针左移 front - 1 return ans这里最容易写错的一步是front的更新顺序。正确的顺序是先使用再自减。如果把front - 1放在bit.add(front, 1)之前最后一次查询就可能写到 0 号槽位要么越界要么答案错乱。我每次写 BIT 相关代码时都会在草稿纸上把 front 的移动轨迹画出来确认它能落在n, n-1, ..., 1这个区间里。4.4 手算验证还是拿官方样例走一遍m 5queries [3, 1, 2, 1]则 n 4槽位一共 9 个。初始value 1 到 5 放在槽位 5、6、7、8、9front 4。查询pos[q]prefix(pos[q])返回移动后3732删 7加 4front 变 31521删 5加 3front 变 22632删 6加 2front 变 11321删 3加 1front 变 0最后占用槽位是 1、2、4、8、9对应的数字分别是 1、2、3、4、5排列又回到了初始状态[1,2,3,4,5]和暴力模拟完全一致。这套手算表在调试 BIT 时非常有用我建议你第一次实现时也这样做不要直接跑 LeetCode 对答案。复杂度上每个查询要做两次add和一次prefix每次都是 O(log(mn))。初始化时做 m 次add总复杂度 O((mn) log(mn))。空间上是 O(mn)其中tree占 O(mn)pos占 O(m)。当 m、n 到 10^5 量级时这个方案依然能扛住。5. 用这几个测试用例收尾暴力、链表、BIT 的通用校验5.1 必测的边界用例我每次写完解法不管暴力还是 BIT都会先跑下面这一组小用例。它们虽然短但能覆盖大部分边界情况输入期望输出说明m1, queries[1][0]最小规模m3, queries[1,2,3][0,1,2]顺序查询每次移动后还能预测m3, queries[3,3,3][2,0,0]同一个元素反复查询m5, queries[5,4,3,2,1][4,4,4,4,4]逆序查询每次都在队尾m5, queries[3,1,2,1][2,1,2,1]官方样例第五个官方样例很容易让人误以为输出是[2,1,2,0]因为最后一步看起来1 应该回到队首为什么返回 1 而不是 0。注意第四步查询前排列是[2,1,3,4,5]1 前面还有 2所以下标是 1。这提醒我们每次查询发生后排列立刻改变不能沿用查询前的想象顺序。5.2 暴力并不丢人但要能说清楚优化空间在真实刷题场景里先用暴力 AC再想优化是非常正常的路线。LeetCode 出这道题的时候数据范围就是让模拟能过的所以只交暴力代码没有任何问题。但如果你是去面试面试官大概率会追问一句如果 m 和queries都很大怎么办这时候你能说出用树状数组维护占用槽位把查询和移动都变成 O(log) 就已经和在背答案的人拉开差距了。很多面试题不是真的要求你现场手写一棵平衡树而是看你能不能把手上的小暴力方案顺着复杂度瓶颈推进到一个可扩展的设计。5.3 同类题怎么迁移这套思路这套固定槽位 BIT的方法本质是两层映射pos数组维护值 - 槽位编号BIT 维护槽位编号 - 当前世界里的排名。凡是遇到某个 key 被移动、但又要频繁查询它当前排名的问题都可以先考虑这个模型。比如 LRU 风格的缓存模拟、任务调度里把某个任务提前、循环队列里动态调整优先级都是同一个骨架。区别只在于如果查询不是提前给出的流式数据那你就不知道要预留多少空槽位这时可以改用动态开点 BIT或者用平衡树维护子树大小。我自己的习惯是遇到复杂度优化题先别急着写高级数据结构而是先把暴力方案画一遍标出瓶颈在哪再看看能不能用离线手段把动态问题转换成静态问题。1409 就是一个很好的例子移动本身不复杂复杂的是移动之后还要知道排名而树状数组恰好擅长在这个场景里给出答案。