class Solution {
public:
int runeReserve(vector<int>& runes) {
}
};
LCP 77. 符文储备
远征队在出发前需要携带一些「符文」，作为后续的冒险储备。runes[i] 表示第 i 枚符文的魔力值。
他们将从中选取若干符文进行携带，并对这些符文进行重新排列，以确保任意相邻的两块符文之间的魔力值相差不超过 1。
请返回他们能够携带的符文 最大数量。
示例 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^40 <= runes[i] <= 10^4原站题解
cpp 解法, 执行用时: 44 ms, 内存消耗: 27.3 MB, 提交时间: 2023-05-08 10:00:13
class Solution {
public:
int runeReserve(vector<int> &runes) {
sort(runes.begin(), runes.end());
int ans = 1, cnt = 1;
for (int i = 1; i < runes.size(); i++)
if (runes[i] - runes[i - 1] > 1)
cnt = 1;
else
ans = max(ans, ++cnt);
return ans;
}
};
golang 解法, 执行用时: 44 ms, 内存消耗: 6.3 MB, 提交时间: 2023-05-08 09:59:56
func runeReserve(runes []int) int {
sort.Ints(runes)
ans, cnt := 1, 1
for i, n := 1, len(runes); i < n; i++ {
if runes[i]-runes[i-1] > 1 {
cnt = 1 // 重新统计
} else if cnt++; cnt > ans {
ans = cnt
}
}
return ans
}
java 解法, 执行用时: 13 ms, 内存消耗: 43.1 MB, 提交时间: 2023-05-08 09:59:43
class Solution {
public int runeReserve(int[] runes) {
Arrays.sort(runes);
int ans = 1, cnt = 1;
for (int i = 1; i < runes.length; i++)
if (runes[i] - runes[i - 1] > 1)
cnt = 1;
else
ans = Math.max(ans, ++cnt);
return ans;
}
}
python3 解法, 执行用时: 116 ms, 内存消耗: 17 MB, 提交时间: 2023-05-08 09:59:31
class Solution:
def runeReserve(self, runes: List[int]) -> int:
runes.sort()
ans = cnt = 1
for pre, cur in pairwise(runes):
if cur - pre > 1:
cnt = 1 # 重新统计
else:
cnt += 1
ans = max(ans, cnt)
return ans