题目内容

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

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

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

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

思路:双指针

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

代码

java

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