教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文基于 AlgoNote 算法通关手册 中的 0358. K 距离间隔重排字符串题解 展开聚焦「贪心 优先队列」这一经典组合在字符串重排约束下的应用。读完本文你将掌握如何用「最大堆 等待队列」在 $O(n \log m)$ 时间内完成带间距约束的字符重排并理解可行性判定的本质这一套路可直接迁移到任务调度、Top-K 高频元素等一批同类面试题。一、题目概览与题意解读1.1 题目信息题号0358. K 距离间隔重排字符串标签贪心、哈希表、字符串、计数、排序、堆优先队列难度困难1.2 题目描述给定一个非空字符串s和一个整数k要求将s中的字母重新排列使得重排后的字符串中相同字母的位置间隔距离「至少」为k。如果无法做到返回空字符串。这里的关键在于理解「间隔距离至少为 k」的含义例如abcabc中两个a分别位于下标0和3它们之间的距离为3满足k 3的约束。1.3 数据范围说明约束项取值范围对算法的影响字符串长度$1 \le s.length \le 3 \times 10^{5}$数据规模较大暴力全排列$O(n!)$完全不可行需要多项式级贪心或构造算法字符集s仅由小写英文字母组成不同字符数 $m \le 26$可用Counter或定长数组统计频率间距参数$0 \le k \le s.length$k 0、k 1时不构成任何约束需要特殊分支处理1.4 示例示例 1输入: s aabbcc, k 3 输出: abcabc 解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。示例 2输入: s aaabc, k 3 输出: 解释: 没有办法找到可能的重排结果。示例 2 直观地展示了可行性判定a出现了 3 次在长度为 5 的字符串中要让任意两个a的距离不小于 3至多只能放下 2 个a例如下标0和3因此必然无解。二、问题建模为什么是「贪心 优先队列」2.1 从约束看贪心动机要使相同字母的间隔足够大最直觉的策略是每次都优先放置「剩余次数最多」的字符。理由在于频率最高的字符最「拥挤」它最容易被后续字符挤到相邻位置而违反间距约束所以必须尽早、尽量均匀地把它铺开放置完高频率字符后用其他低频率字符填充它留下的空位相当于把「最难处理的资源」优先调度掉。这正是贪心选择性质的体现每一步都做当前局部最优的选择取剩余频率最高的字符并通过「等待队列」的冷却机制保证不回头、不回溯最终累积出全局可行的重排。关于贪心算法「贪心选择性质」与「最优子结构」两大特征的理论铺垫可参考仓库中的 贪心算法基础篇。2.2 为什么需要最大堆优先队列「每次取频率最高的字符」这一需求需要一种能动态维护最大值、支持插入与删除的数据结构如果用普通数组每次取最大值需要 $O(m)$ 遍历总复杂度退化为 $O(nm)$二叉堆实现的优先队列入队heappush与出队heappop均为 $O(\log m)$整体复杂度最优。在仓库的 优先队列教程 中明确指出二叉堆实现下入队、出队均为 $O(\log n)$是三种实现方式数组、链表、二叉堆中综合效率最高的方案。Python 标准库heapq默认实现的是最小堆因此在本题中需要通过「取负数」的技巧把它改造成最大堆——这与仓库文档中「如果需实现大顶堆可将优先级取负数存入堆中」的用法完全一致。2.3 本题的算法家族定位0358 是「间距约束重排」问题家族中的典型成员在仓库中可以找到它的近亲0621. 任务调度器同类任务之间需要n单位冷却时间求最短执行时间同样是「频率最高的任务优先 冷却间隔」模型0767. 重构字符串要求相邻字符不同即本题k 2的特例0347. 前 K 个高频元素展示了用堆按频率取 Top-K 的同类手法。三、核心思路贪心 优先队列 等待队列3.1 问题分析统计频率遍历s统计每个字符的出现次数freq[c]维护最大堆将「(负频率, 字符)」二元组放入优先队列堆顶永远是当前剩余次数最多的字符维护等待队列用先进先出的deque记录「最近被使用过的字符及其剩余次数」作为冷却窗口距离约束只有当某个字符离开等待队列即它已经与最近一次放置相隔了k个位置时才允许它重新参与「下一轮放置」的竞争。3.2 算法步骤统计频率遍历字符串s统计每个字符c的出现次数freq[c]。构建优先队列将所有字符按频率降序放入优先队列最大堆。贪心放置每次从优先队列中取出频率最高的字符将该字符追加到结果末尾同时把「(剩余次数, 字符)」压入等待队列代表它进入冷却期当等待队列长度达到k时队首字符已满足「与上次放置相隔 k 个位置」的条件将其弹出若它仍有剩余次数则重新压入优先队列参与后续竞争。检查可行性如果最终结果长度等于原字符串长度说明所有字符都被成功放置返回结果否则返回空字符串。3.3 关键变量说明变量类型作用freq[c]Counter字符c的出现频率max_heap列表最大堆以「负频率」存储字符堆顶即当前剩余次数最多的字符wait_queuedeque等待队列记录最近使用过的字符及其剩余次数充当冷却窗口result列表结果字符串的字符序列需要指出的是原题解中提到的used_chars最近使用的字符集合在最终实现中并不需要单独维护——wait_queue本身就是「最近使用的字符」的完整记录它既保证了间距约束又承担了释放字符回堆的职责。四、完整代码实现含逐行注释import heapq from collections import Counter, deque class Solution: def rearrangeString(self, s: str, k: int) - str: # 特殊情况k 1 时不存在间距约束原字符串本身即满足条件 if k 1: return s # 统计字符频率 freq Counter(s) # 构建最大堆Python heapq 为最小堆使用负数实现最大堆 # 堆元素为 (负频率, 字符)频率相同时按字符字典序比较行为确定 max_heap [] for char, count in freq.items(): heapq.heappush(max_heap, (-count, char)) # 等待队列存储最近使用的字符及其剩余次数 wait_queue deque() result [] while max_heap: # 取出频率最高的字符 neg_count, char heapq.heappop(max_heap) count -neg_count # 将字符添加到结果中 result.append(char) # 将使用过的字符剩余次数减 1加入等待队列进入冷却期 wait_queue.append((count - 1, char)) # 等待队列长度达到 k 时最早使用的字符已与上次放置相隔 k 个位置 # 冷却结束可以重新参与放置若仍有剩余次数则重新入堆 if len(wait_queue) k: old_count, old_char wait_queue.popleft() if old_count 0: heapq.heappush(max_heap, (-old_count, old_char)) # 检查是否所有字符都被使用结果长度等于原串长度说明重排成功 if len(result) len(s): return .join(result) else: return 4.1 代码细节解读负频率技巧heapq是最小堆将-count作为排序键后堆顶恰为频率最高的字符。这一手法与仓库 优先队列教程 中PriorityQueue类的push实现heapq.heappush(self.queue, (-priority, self.index, item))同源。二元组排序行为当多个字符频率相同时heapq会继续比较第二个元素字符因此(-2, a) (-2, b)弹出顺序确定且可复现不会引入随机性。等待队列的释放条件代码中判定为len(wait_queue) k。原题解注释写作「达到 k-1」实际代码逻辑以k为准——当队列长度恰好为k时队首字符自上次放置以来已经隔了k个字符位恰好满足「间隔距离至少为 k」的约束。剩余次数为 0 的字符从等待队列弹出后若old_count 0说明该字符已用完直接丢弃不再入堆。堆空但结果未满while max_heap循环以堆空为终止条件。当堆提前为空时等待队列中可能还残留old_count 0的字符它们永远等不到冷却结束此时len(result) len(s)最终返回。这正是示例 2 无解的表现形式。五、示例逐步推演5.1 示例 1s aabbcc, k 3初始频率a 2, b 2, c 2初始堆[(-2,a), (-2,b), (-2,c)]弹出顺序为a → b → c。步骤弹出字符剩余次数当前 resultwait_queue是否释放回堆1a1a[(1,a)]否长度 1 32b1ab[(1,a),(1,b)]否长度 2 33c1abc[(1,a),(1,b),(1,c)]是弹出(1,a)入堆4a0abca[(1,b),(1,c),(0,a)]是弹出(1,b)入堆5b0abcab[(1,c),(0,a),(0,b)]是弹出(1,c)入堆6c0abcabc[(0,a),(0,b),(0,c)]弹出(0,a)剩余 0 不入堆堆空后len(result) 6 len(s) 6返回abcabc。注意下标0与3处的a、下标1与4处的b、下标2与5处的c间距均为3完美满足约束。5.2 示例 2s aaabc, k 3初始频率a 3, b 1, c 1初始堆[(-3,a), (-1,b), (-1,c)]。步骤弹出字符剩余次数当前 resultwait_queue是否释放回堆1a2a[(2,a)]否2b0ab[(2,a),(0,b)]否3c0abc[(2,a),(0,b),(0,c)]是弹出(2,a)入堆4a1abca[(0,b),(0,c),(1,a)]弹出(0,b)剩余 0 不入堆第 4 步结束后堆已为空但(1,a)仍滞留在等待队列中无法被释放循环终止。len(result) 4 ! len(s) 5返回。这与直觉一致3 个a在长度 5 的字符串中按间距≥ 3的要求最多只能放下 2 个。5.3 可行性预判可选优化在进入贪心循环之前可以先做一次必要条件的快速预判若某个字符的出现次数max_count (n k - 1) // k其中n len(s)则必然无解可直接返回避免无谓的堆操作。需要强调的是该条件只是必要条件而非充分条件最终仍需以「构造结果长度是否等于n」作为权威判定依据。示例 2 中(5 3 - 1) // 3 2 3预判即可提前否决。六、复杂度分析时间复杂度$O(n \log m)$其中 $n$ 为字符串长度$m$ 为不同字符的数量本题中 $m \le 26$。每个字符在堆与等待队列之间至多流转 $O(n)$ 次每次入堆/出堆操作均为 $O(\log m)$。空间复杂度$O(m)$其中 $m$ 为不同字符的数量用于存储字符频率表、优先队列和等待队列。由于 $m \le 26$堆操作的实际开销极小瓶颈主要在 $O(n)$ 的字符扫描与拼接上因此该解法可以轻松应对 $3 \times 10^5$ 的数据规模。七、仓库配套资料与延伸学习7.1 优先队列与堆的底层实现本解法直接使用 Python 标准库heapq若想深入理解二叉堆的底层原理可以对照仓库中的两份资料优先队列教程系统讲解优先队列的三种实现方式对比数组、链表、二叉堆并给出基于heapq的带稳定性优先队列封装手写二叉堆源码完整实现了heapAdjust堆调整、heapify建堆、heappush入队、heappop出队与heapSort其中heappush自下而上调整、heappop先交换堆顶与末尾再自上而下调整的过程正是heapq库内部行为的原理解释。7.2 贪心算法方法论如果希望系统掌握贪心算法的「三步走」问题转化 → 贪心策略制定 → 最优子结构利用以及正确性证明思路数学归纳法、交换论证法可阅读仓库中的 贪心算法基础篇。7.3 同类题目进阶练习在仓库题解集中与本题共享「频率 间距约束 堆」模型的题目还有0621. 任务调度器把「字符重排」换成「CPU 任务调度」把「返回可行重排」换成「求最短完成时间」解法演变为「峰值频率 × 冷却窗口 溢出任务数」的公式法可作为对比思考0767. 重构字符串即本题k 2的特例相邻字符不同其中给出的max_count (n 1) // 2判定与 5.3 节的预判公式同源0347. 前 K 个高频元素展示用优先队列按频率排序的姊妹技巧。建议的练习路径先手写并跑通 0767特例再完成 0358一般化最后用 0621 验证对同一模型从「构造解」到「计数解」的视角切换即可牢固掌握这一高频面试套路。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0502 IPO——贪心策略与优先队列堆实现最大资本化AlgoNote 算法通关手册LeetCode 0502 IPO——贪心策略与优先队列堆实现最大资本化 LeetCode 0502「IPO」是「算法通关手教程文档知识库LeetCode 0632 最小区间覆盖 K 个列表题解AlgoNote 算法通关手册的堆优先队列实战解析LeetCode 0632 最小区间覆盖 K 个列表题解AlgoNote 算法通关手册的堆优先队列实战解析 导读 本题是「 AlgoNote 算法通关教程文档知识库AlgoNote 题解LeetCode 0767 重构字符串——贪心策略与最大堆的实战实现AlgoNote 题解LeetCode 0767 重构字符串——贪心策略与最大堆的实战实现 本篇题解基于「算法通关手册AlgoNote」仓库中的 重构字符教程文档知识库上一篇Wan2GP Windows AMD 安装指南基于 TheRock ROCm PyTorch 的 RDNA 2/3/3.5/4 部署实战下一篇DSH 启动失败自救指南dsh-market 恢复面板带你一键逃出全有全无的启动死局创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考