doocs/leetcode 题解：LCP 77. 符文储备——排序 + 滑动窗口求相邻魔力值差不超过 1 的最长可携带符文序列-平芜编程栈

示例工程

【免费下载链接】leetcode

🔥LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

导读：本文围绕 LeetCode LCP 系列题「LCP 77. 符文储备」展开，完整讲解题目的约束条件、两个官方示例，并深入剖析其核心解法——先将符文魔力值排序，再用双指针维护滑动窗口，找出「相邻魔力值相差不超过 1」的最长连续段。读完本文，你将掌握该类「差值约束 + 最大化子集」问题的通用建模思路，并能对照 doocs/leetcode 仓库中 Python、Java、C++、Go、TypeScript 五种语言的官方题解与源码独立编写和验证代码。

一、题目描述

远征队在出发前需要携带一些「符文」，作为后续的冒险储备。runes[i]表示第i枚符文的魔力值。

他们将从中选取若干符文进行携带，并对这些符文进行重新排列，以确保任意相邻的两块符文之间的魔力值相差不超过1。

请返回他们能够携带的符文最大数量。

输入：runes = [1,3,5,4,1,7] 输出：3

本题来自 LeetCode LCP（力扣杯 / 程序员面试）系列，在仓库中的编号为「LCP 77. 符文储备」，难度为简单，是一道典型的「排序 + 滑动窗口 / 双指针」应用题。

二、示例与数据范围

示例 1：

输入：runes = [1,3,5,4,1,7]
输出：3
解释：最佳的选择方案为[3,5,4]，将其排列为[3,4,5]后，任意相邻的两块符文魔力值均不超过1，携带数量为3。其他满足条件的方案为[1,1]和[7]，数量均小于3，因此返回可携带的最大数量3。

示例 2：

输入：runes = [1,1,3,3,2,4]
输出：6
解释：排列为[1,1,2,3,3,4]，可携带所有的符文。

提示：

1 <= runes.length <= 10^4
0 <= runes[i] <= 10^4

从数据范围可以判断：n最大为10^4，魔力值是非负整数且值域上限同样为10^4。这决定了我们既可以选择O(n log n)的排序类算法，也保留了值域受限时「桶计数」优化的想象空间（见后文第七节）。

三、核心思路：把「可重新排列」转化为排序后的连续段

题目的难点在于：约束条件是「重新排列后任意相邻两块差值不超过 1」，这似乎与排列顺序有关。但仔细观察可以发现一个关键事实：

对于任意一组选取的符文，把它们按魔力值从小到大排序，恰好是让相邻差值最小的排列方式。因此，一个选取方案合法，当且仅当它排序后任意相邻两项的差都不超过 1。

原文档的「思考」部分也给出了同样的分析：

n <= 10^4，要求选出一个子集，任意两块魔力差的绝对值不超过1，并最大化子集大小；
差值条件与顺序无关，排序后合法元素必落在一段连续区间；
排序后用左端i维护当前段：相邻差大于1则重开窗口，否则用j - i + 1更新答案。

进一步推导：假设排序后的数组中存在三个元素a <= b <= c，如果c - a <= 1，那么必然有b - a <= 1且c - b <= 1，即中间的元素一定也能被纳入同一个合法集合。这意味着：任何一个合法的携带方案，都对应于排序后数组中的一段连续区间；反过来，排序后任意一段「相邻差均不超过 1」的连续区间，其全部元素构成的集合都是合法方案。

于是问题被干净地转化为：

在排序后的runes数组中，寻找「相邻元素之差均不超过 1」的最长连续子数组的长度。

四、方法一：排序 + 滑动窗口（双指针）

4.1 算法流程

将runes按魔力值从小到大排序；
初始化窗口左端i = 0，答案ans = 0；
用右端j从左到右遍历排序后的数组：
- 若j > 0且runes[j] - runes[j-1] > 1，说明当前元素与前一个元素「断档」，合法段被切断，令i = j重开窗口；
- 否则，窗口[i, j]内的相邻差均不超过 1，用窗口长度j - i + 1更新ans；
遍历结束后，ans即为可携带的最大符文数量。

正确性说明：由于合法集合在排序后必然是连续段，而相邻差超过 1 的「断点」一定是两个合法段的天然分界，因此每次断档时重开窗口，就能枚举出所有可能的合法段，取其中长度最大者即为答案。

4.2 复杂度分析

按原文档给出的结论：

时间复杂度：O(n × log n)，主要来自排序；
空间复杂度：O(log n)，来自排序过程（如快速排序的递归栈开销）。

其中n是数组runes的长度。排序之后的双指针扫描是单趟O(n)，不是性能瓶颈。

五、多语言实现与逐行解读

该题在仓库目录 lcp/LCP 77. 符文储备下提供了五种语言的独立实现文件：Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts，与 README 中的题解代码一一对应。下面逐一解读。

5.1 Python3

参考源码：Solution.py

class Solution: def runeReserve(self, runes: List[int]) -> int: runes.sort() ans = i = 0 for j, x in enumerate(runes): if j and runes[j] - runes[j - 1] > 1: i = j else: ans = max(ans, j - i + 1) return ans

要点说明：

runes.sort()原地升序排序，i为窗口左端，ans为答案；
enumerate同时给出下标j与元素值x（x即runes[j]，用于与runes[j-1]比较）；
if j and ...利用了 Python 中0为假值的特性：当j == 0（第一个元素）时条件短路为假，进入else分支，将ans置为1——这保证了对单元素窗口的处理；
当相邻差大于 1 时i = j重开窗口；否则用j - i + 1更新最大长度。

5.2 Java

参考源码：Solution.java

class Solution { public int runeReserve(int[] runes) { Arrays.sort(runes); int ans = 0; for (int i = 0, j = 0; j < runes.length; ++j) { if (j > 0 && runes[j] - runes[j - 1] > 1) { i = j; } else { ans = Math.max(ans, j - i + 1); } } return ans; } }

要点说明：

Arrays.sort(runes)对int[]原地排序；
双下标i（窗口左端）与j（扫描指针）在同一循环内声明，j即窗口右端；
与 Python 版本逻辑完全一致：j > 0时若runes[j] - runes[j-1] > 1则i = j重开窗口，否则Math.max更新答案。

5.3 C++

参考源码：Solution.cpp

class Solution { public: int runeReserve(vector<int>& runes) { sort(runes.begin(), runes.end()); int ans = 0; for (int i = 0, j = 0; j < runes.size(); ++j) { if (j && runes[j] - runes[j - 1] > 1) { i = j; } else { ans = max(ans, j - i + 1); } } return ans; } };

要点说明：

sort(runes.begin(), runes.end())对vector<int>升序排序；
if (j && ...)与 Python 写法同源：j == 0时短路跳过断档判断，进入else分支初始化答案；
注意j是size_t类型时j - 1需保证j > 0才参与运算，该写法通过短路求值规避了无符号下溢问题。

5.4 Go

参考源码：Solution.go

func runeReserve(runes []int) (ans int) { sort.Ints(runes) i := 0 for j, x := range runes { if j > 0 && x-runes[j-1] > 1 { i = j } else if t := j - i + 1; ans < t { ans = t } } return }

要点说明：

sort.Ints(runes)原地排序；
函数使用具名返回值(ans int)，因此末尾直接return即可返回ans；
range runes同时给出下标j与元素值x，断档判断直接比较x与runes[j-1]；
更新答案时使用 Go 特色的else if短语句：在条件内声明局部变量t := j - i + 1，当ans < t时赋值，写法紧凑且作用域清晰。

5.5 TypeScript

参考源码：Solution.ts

function runeReserve(runes: number[]): number { runes.sort((a, b) => a - b); let ans = 0; let i = 0; for (let j = 0; j < runes.length; ++j) { if (j > 0 && runes[j] - runes[j - 1] > 1) { i = j; } else { ans = Math.max(ans, j - i + 1); } } return ans; }

要点说明：

runes.sort((a, b) => a - b)必须显式传入比较器：JS/TS 默认的Array.prototype.sort按字符串字典序排序，直接调用sort()会把10排在2前面，导致数值排序错误，这是本题最容易踩的坑；
其余逻辑（双指针、断档重开窗口、Math.max更新）与其他语言一致。

六、边界情况与易错点

结合题目约束与源码实现，以下几个边界值得特别注意：

场景	行为	说明
`runes`只有一个元素	返回`1`	首轮`j == 0`走`else`分支，`ans`被置为`1`，与「任意相邻」约束空集无关，单独一块符文必可携带
所有魔力值相同（如`[5,5,5]`）	返回`n`	相邻差为`0 <= 1`，全程不断档，窗口覆盖整个数组
存在重复值（如`[1,1,2,2]`）	差值`0`合法	重复值之间的差为 0，不触发断档，可全部纳入同一窗口
魔力值为`0`	合法	`0 <= runes[i] <= 10^4`，`0`与`1`的差为`1`，可正常参与窗口计算
相邻差恰好为`1`	不断档	断档条件严格为`> 1`，差等于`1`时窗口继续扩展
相邻差大于`1`时	重开窗口	断点处`i = j`，当前元素单独成段，其长度由后续轮次的`else`分支计入

最易出错的点：TypeScript/JavaScript 中忘记传(a, b) => a - b比较器，导致数值排序变成字典序排序；以及判断断档时误用「窗口内最大值与最小值之差」而非「相邻元素之差」——本题约束的是相邻两块差值不超过 1，而非整个窗口跨度，两者含义完全不同。

七、思路延伸：值域受限下的桶计数等价实现

题目提示中0 <= runes[i] <= 10^4，即魔力值是非负整数且值域有限。从第三节的结论可以推导出一个等价的视角：

由于魔力值是整数，且排序后相邻差不超过 1，合法集合的不同魔力值必然构成一段连续的整数区间（区间内每个值可出现任意多次）。

由此可以得到一种不排序的替代实现思路：先统计每个魔力值v的出现频次cnt[v]，然后扫描值域，找出「频次大于 0 的连续整数区间」中最长的一段，区间携带数量即为该区间内所有频次之和。其复杂度为O(n + M)（M为值域上限10^4），在n接近10^4时与排序方案相当，但当n远大于值域时（例如大量重复数据），桶计数可以省去排序的O(n log n)开销。

需要说明的是：该变体是基于题目约束自行推导的等价思路，仓库官方题解采用的是前述「排序 + 滑动窗口」方案；两种方法结论一致，可以互为验证。

八、仓库资源速览

本主题在仓库中的完整资源如下，便于对照学习与验证：

题解文档（题目描述 + 解法 + 全语言代码）
Solution.py（Python3 实现）
Solution.java（Java 实现）
Solution.cpp（C++ 实现）
Solution.go（Go 实现）
Solution.ts（TypeScript 实现）
LCP 系列题解索引（可按题号快速定位全部 LCP 题解）

总结

「LCP 77. 符文储备」表面上是带排列约束的选取问题，核心洞察在于两点：一是排序是让相邻差最小的最优排列，使「任意相邻差 ≤ 1」与顺序解耦；二是合法集合必然对应排序数组中的连续段，从而把问题归约为「找相邻差均 ≤ 1 的最长连续子数组」。基于此，排序 + 双指针滑动窗口即可在O(n log n)时间内求解，五种语言的实现结构完全一致，唯一需要注意的差异点是 JS/TS 的排序比较器。该题的「先排序消解顺序约束、再双指针扫连续段」套路，同样适用于其他「差值 / 间隔约束 + 最大化子集」类问题，值得熟练掌握。