
本文介绍一种高效算法,用于统计给定整数列表中最多可构成多少个长度为5、严格递增(即形如 a₁本文介绍一种高效算法,用于统计给定整数列表中最多可构成多少个长度为5、严格递增(即形如 a₁
原问题本质并非检测“连续相等元素”,而是识别严格递增的五元组(staircase sequence):每个五元组必须满足 x₁ [1,1,1,2,2,3,3,3,4,4,4,5,5] 中可提取两个完整阶梯
[1,2,3,4,5](例如取第0、3、5、8、11位,再取第1、4、6、9、12位),剩余[1,3,4]无法再构成第五个元素,故结果为2。原代码存在根本性误解:
- 它错误地将
consecutiveCount用于统计相邻相等值,却期望解决跨重复值的递增匹配;- 更严重的是逻辑漏洞:当
consecutiveCount == 5时重置为0,会导致后续计数错乱(如6个相同数会触发两次count++),且完全忽略“升序”要求。✅ 正确解法应采用贪心多指针匹配(类似“分发饼干”思想):维护5个计数器
cnt[0..4],分别记录当前已匹配到第1/2/3/4/5位的候选序列数量。遍历每个数字x时,尝试将其作为某一级台阶:
- 若
x可接在已有长度为4的序列后 →cnt[4]++- 否则,若可接在长度为3的序列后 →
cnt[3]++- …以此类推,优先填充更长的序列(贪心最优);
- 特别地,
x总可作为新序列的第1位 →cnt[0]++但注意:由于要求严格递增,我们只允许
x接在上一阶值严格小于x的序列之后。因此需按值分组处理,并对每组x逆序更新cnt[4]→cnt[0],避免同一轮中用刚更新的cnt[i-1]影响cnt[i]。以下是健壮、可读的 Java 实现:
import java.util.*; public static int countOrderedFives(List<Integer> list) { if (list == null || list.size() < 5) return 0; // cnt[i] 表示当前已构建到第 i+1 阶(0-indexed)的序列数量 long[] cnt = new long[5]; // 使用 long 防止大输入溢出 // 按值分组:key=数值,value=该值出现频次 Map<Integer, Integer> freq = new HashMap<>(); for (int x : list) { freq.put(x, freq.getOrDefault(x, 0) + 1); } // 按键升序遍历(保证处理顺序符合递增要求) List<Integer> sortedKeys = new ArrayList<>(freq.keySet()); Collections.sort(sortedKeys); for (int x : sortedKeys) { int countX = freq.get(x); // 关键:逆序更新,确保用的是上一轮的 cnt[i-1] // 即:先用 cnt[3] 构建新 cnt[4],再用 cnt[2] 构建 cnt[3]... // 这样避免把同一个 x 同时用作多个位置 for (int i = 4; i >= 1; i--) { long canExtend = Math.min(countX, cnt[i - 1]); cnt[i] += canExtend; countX -= canExtend; if (countX == 0) break; } // 剩余的 x 全部作为新序列起点 cnt[0] += countX; } return (int) cnt[4]; // 所有完成5阶的序列总数 }? 关键注意事项:
- 时间复杂度:O(n + k log k),k 为不同数值个数,远优于暴力回溯;
- 空间复杂度:O(k),仅需哈希表存频次;
- 贪心正确性:逆序更新确保“尽可能复用已有长序列”,是经典匹配最优策略(参考 LeetCode 659. Split Array into Consecutive Subsequences);
- 边界处理:空列表、长度不足5直接返回0;使用
long避免中间计数溢出;- 不支持非严格递增:本解法严格要求
,若需 <code>≤(非降序),只需修改分组逻辑为按索引顺序扫描并动态维护5个指针。总结:解决此类“有序子序列计数”问题,核心在于脱离“相邻比较”思维,转向状态机式分层计数 + 贪心扩展。原代码混淆了“连续相等”与“全局有序”的语义,而正确路径是抽象出5层匹配状态,让每个新元素在满足递增前提下,尽其所能向上填充——这既是算法的精妙之处,也是工程实践中避免逻辑错位的关键范式。

















