分数: 466 分
问题陈述
Takahashi 正在分析天气数据。他有体温记录 N 天,当天的气温 i (1 \leq i \leq N) is A_i 度。
Takahashi 希望找到温度稳定的时期。当一对整数 (l, r) 满足 1 \leq l \leq r \leq N,连续 r - l + 1 天数 l 到今天 r 被称为“句点”。当一段时间内最高温度和最低温度之间的差异最大时,称一段时间是“稳定的” K,即当
\max(A_l, A_{l+1}, \ldots, A_r) - \min(A_l, A_{l+1}, \ldots, A_r) \leq K
成立。
1 天期间,其中 l = r,最大值和最小值相等,因此差值为 0。在这个问题的约束下,哪里 K \geq 0,这样的时期总是稳定的。因此,至少有 N 稳定期。求最长稳定期的天数。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N K A_1 A_2 \ldots A_N
- 第一行包含天数 N 中温度记录及上限 K 的温差要考虑稳定,中间用空格隔开。
- 第二行包含每天的温度 A_1, A_2, \ldots, A_N,用空格分隔。
输出
在一行中打印稳定期的最大天数。
示例输入 1
7 3 20 22 21 23 19 25 24
示例输出 1
4
示例输入 2
10 5 15 18 12 14 16 20 19 17 22 25
示例输出 2
4
示例输入 3
15 10 -5 0 3 -2 5 8 2 -1 4 20 25 22 28 30 18
示例输出 3
8