华为 · 滑动窗口 · 算法编程题
华为 滑动窗口 n ≤ 1e5 时限 2 秒 / 256 MB

题目描述

小红正在监控一排设备的运行状态。每台设备都有一个状态值,她希望找到一段连续设备,使得这段设备中任意两台设备的状态值差的绝对值都不超过 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 。

样例共 1 组

样例 1
输入
9 3
1 4 2 5 7 4 3 8 1
输出
1 3

算法解析依据充分

考点:滑动窗口

数据规模 n ≤ 1e5 | 限制 2 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:n ≤ 1e5
  • 元素值域:d ≤ 1e4,a_i ≤ 1e4(注意整数类型选择,避免溢出)
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:2 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:滑动窗口

本题切入点

最长区间且区间内 max−min ≤ d:双指针(滑动窗口)配合单调队列维护窗口极值,窗口不合法时收缩左端;最终取最长且起点编号最小的区间。

维护一个连续区间,进一个元素出一个元素,区间内统计量增量更新。

思路框架(滑动窗口 通法 · 非本题专属)

  1. 用左右指针确定一个窗口 [l, r]。
  2. 右端点右移:把新元素加入窗口统计。
  3. 当窗口违反约束(长度超限 / 含重复等)时,左端点右移,把元素移出统计。
  4. 在每个合法窗口上更新答案。
  5. 统计量用哈希表或计数数组维护,避免每次重算。

实现要点:注意窗口长度是定长还是不定长:定长则区间长度固定为 k,不定长则靠条件收缩。

复杂度:时间 O(n) | 空间 O(字符集/去重元素数)

该范式的通法易错点

  • 移出窗口时忘同步更新统计量。
  • 窗口长度与下标边界差 1(长度 k 对应 r-l+1)。

对照本题

  • 数据规模 n ≤ 1e5,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入:9 3 / 1 4 2 5 7 4 3 8 1
  • 输出:1 3

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2026年-华为-05月09号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解