Problem 5E. 限制子数组的最大长度

Problem 5E. 限制子数组的最大长度

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 5E. 限制子数组的最大长度

时间限制:1s

空间限制:256MB

题目背景

\(tsingpig\) 对子数组的性质很感兴趣。

题目描述

给定一个整数数组\(nums\) 和一个整数\(k\) , 把\(nums\)的连续非空子数组中满足其**任意两个元素差的绝对值小于等于\(k\)** 的称为限制子数组。

求限制子数组的最大长度,若不存在返回0。

输入格式

  • 第一行有2个整数\(n, k\),其中\(n\) 表示\(nums\) 的长度。
  • 第二行\(n\) 个整数,构成数组\(nums\)。

输出格式

输出一行一个整数,限制子数组的最大长度,不存在返回0。

样例输入 1

4 4
8 2 4 7

样例输出 1

2

解释:所有子数组如下:
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此,满足题意的最长子数组的长度为 2 。

样例输入 2

8 0
4 2 2 2 4 4 2 2

样例输出 2

3

最长的限制子数组是[2, 2, 2]

数据范围及限制

对于60%的数据,\( n \in [1,10^5]\)

对于100%的数据,\( n \in [1,5\times 10^6] \)

\( nums[i] \in [0, 10^9] , k \in [0, 10^9]\)

2023秋 悬赏令第五周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-11-05 18:30
结束于
2023-11-12 00:00
持续时间
149.5 小时
主持人
参赛人数
71