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
数据范围及限制
对于全部数据:\( nums[i] \in [0, 10^9] , k \in [0, 10^9]\)
对于60%的数据,\( n \in [1,10^5]\)
对于100%的数据,\( n \in [1,5\times 10^6] \)
信息
- ID
- 1003
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 1
- 已通过
- 1
- 通过率
- 100%
- 上传者