小红正在监控一排设备的运行状态。每台设备都有一个状态值,她希望找到一段连续设备,使得这段设备中任意两台设备的状态值差的绝对值都不超过 d。 请找出满足条件的最长连续区间。如果有多个长度相同的区间,输出起始编号最小的那个。设备编号从 1 开始。 若最长区间长度为 1,也按要求输出对应的单点区间。
第一行:两个整数 n,d ( 1 ≤ n ≤ 100000, 0 ≤ d ≤ 10000 ),分别表示设备数量和允许的最大状态差值。 第二行: n 个整数,表示 n 台设备的运行状态值 a_1,a_2,...,a_n ( 1 ≤ a_i ≤ 10000 )。
输出两个整数 L, R ,表示最长连续设备序列的起始和结束编号(第一台设备编号为1)。 如果有多个长度相同的序列,输出起始编号最小的序列。 如果只有1台设备,或不存在满足条件的序列(任何两个相邻的设备的运行状态值之差的绝对值都超过 d ),则输出 11 。
9 3 1 4 2 5 7 4 3 8 1
1 3
考点:滑动窗口
数据规模 n ≤ 1e5 | 限制 2 秒 / 256MB | 标准输入输出
推荐方向:滑动窗口
本题切入点
最长区间且区间内 max−min ≤ d:双指针(滑动窗口)配合单调队列维护窗口极值,窗口不合法时收缩左端;最终取最长且起点编号最小的区间。
维护一个连续区间,进一个元素出一个元素,区间内统计量增量更新。
思路框架(滑动窗口 通法 · 非本题专属)
实现要点:注意窗口长度是定长还是不定长:定长则区间长度固定为 k,不定长则靠条件收缩。
复杂度:时间 O(n) | 空间 O(字符集/去重元素数)
该范式的通法易错点
对照本题
样例 1
9 3 / 1 4 2 5 7 4 3 8 11 3解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2026年-华为-05月09号开发岗。