← 返回题目列表

AtCoder · awc0058_e

E. 温度稳定期

中文机器翻译题面 查看原题

分数: 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