携程 9.20 Java 开发笔试：两道编程题与一道 AI 题

《面试题目》

1. 一串数里每三个相邻数为一组，组与组之间不能重叠，若一组内的最大值与最小值之差小于 d 就计为一组，最多能分出多少组？

《参考解析》

第一题：定长区间的贪心

“三个相邻数一组、组间不能重叠”，等价于在序列上挑出若干不重叠、长度为 3 的区间，使满足条件的区间数最多。

所有候选区间长度相同，所以“能取就取最靠前的一个”就是最优解：从下标 0 开始扫描，检查 [i, i+2] 这一段的最大值与最小值之差是否小于 d；满足就计数并把 i 前进 3，不满足就前进 1。可以用交换论证说明它为什么对——最靠前的可行区间右端点最小，留给后面序列的空间只会更多，换成任何别的选择都拿不到更多组。

每个下标最多被算一次窗口极值，整体 O(n)；窗口固定为 3 个元素，也不需要额外的单调队列。

这道题为什么容易大面积掉分

原帖没有写错误原因，只留下“简单，但不知道为什么 37%”。这类“看着简单却过不了”的题，常见原因有三类：一是每个窗口都重新扫一遍求极值，n 很大时超时；二是边界写错，比如把“小于 d”写成“小于等于 d”，或者把“不能重叠”理解成“不能相邻”；三是序列不足 3 个元素、d 为 0、数值范围导致差值溢出这类用例没有单独处理。这些是排查方向，不是原帖确认过的结论。

第二题与 AI 题的记录边界

第二题原帖只留了作者自己的思路——“不能一次到达时，先迈一大步再退回一小步，或者干脆只走小步”——步长规则、起点终点条件和要求都没有保留，无法还原成完整题目。AI 题也只写了“因为编程完蛋了，就随便做了一下”，没有记录题型和内容。这两处不臆造题面。