思路:双指针

使用滑动窗口维护当前区间的最大值和最小值，通过双端队列高效更新。当新增元素导致最大值与最小值的差超过k时，当前区间作为一个分组，分组数增加，并从当前元素重新开始新的窗口。这样确保分组数最少。

代码

java

import java.io.BufferedReader;
import java.io.IOException;

题目内容

有$n$个物品，第$i$个物品的价值为$a_i$。

现在要给这些物品分组，每一组必须是一个下标连续的区间。

同时，每一组内的物品差距不能太大，即任意一组内物品的最大价值减去最小价值不能超过某个给定的常数$k$。

给定这些物品，请问最少要分几组?

输入描述

第一行两个整数 $n,k(1 ≤n≤ 10^5 ,0 ≤k≤ 10^9)$，表示物品的数量及给定的常数。

第二行$n$个整数 $a (0 ≤ a_i ≤ 10^9)$，表示物品的价值。

输出描述

输出一行一个整数，表示最少的分组数。

样例1

输入

4 1
1 3 1 4

输出

4

说明

样例2

输入

4 2
1 3 1 4

输出

2

说明