第1题-平稳风段

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

题意要求的是最长的连续子数组 $[l,r]$ ，使得区间内每一对相邻元素的差的绝对值都不超过阈值 $d$ 。等价于：在序列上从左到右走，只要 $|a_{i+1}-a_i|\le d$ 就可以把 $a_{i+1}$ 接在当前段末尾，否则必须从 $a_{i+1}$ 重新开始一段。
因为“能否延伸”只与上一项有关，具有无后效性，不需要动态规划或数据结构，单次线性扫描即可。
维护当前段长度 cur：若 $|a_i-a_{i-1}|\le d$ 则 cur += 1，否则 cur = 1（新段至少包含当前点）。答案为扫描过程中 cur 的最大值。注意 $n\ge 1$ 时答案至少为 $1$ 。
多组测试数据下，题目保证所有组的 $n$ 之和不超过 $2\times 10^5$ ，因此对每组做 $O(n)$ 扫描，总时间 $O(\sum n)$ ，可以通过。

给定长度为 $n$ 的风速序列 $a_1,a_2,\ldots,a_n$ 和阈值 $d$ 。
定义连续段 $[l,r]$ 为“平稳段”，当且仅当对所有
$i \in [l,r-1]$ 都有： $|a_{i+1}-a_i| \le d$
请你输出所有平稳段的最大长度。

每个测试文件包含多组测试数据。第一行输入一个整数
$T(1 \le T \le 2 \times 10^5)$ 表示数据组数，每组测试数据描述如下：

第一行输入两个整数 $n$ 和
$d(1 \le n \le 2 \times 10^5,\ 0 \le d \le 10^9)$ 。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (|a_i| \le 10^9)$ 。
保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$ 。

对于每组测试数据，输出一行一个整数，表示最大平稳段的长度。

输入

输出

3
1

请从“运行结果”或“历史提交”选择一条记录

选择提交后开始分析