本文最后更新于 445 天前，其中的信息可能已经有所发展或是发生改变。
1824. 钻石收藏家(双指针模板)
原题链接
奶牛贝茜非常喜欢闪闪发光的东西，她会在业余时间开采钻石。
她收藏了 N 颗大小不等的钻石，她想将其中的一些摆放在牛棚的展示柜当中。
为了使展示柜中的钻石尺寸大小相似，她不会将两颗尺寸大小相差超过 K 的钻石同时放在柜子中（刚好相差 K，则没有问题）。
给定 K，请帮助贝茜计算在展示柜中最多可以摆放多少颗钻石。
输入格式
第一行包含两个整数 N,K。
接下来 N 行，每行包含一个整数，表示一颗钻石的尺寸。
输出格式
输出贝茜可以在展示柜中展示的钻石最大数量。
数据范围
1≤N≤1000， 0≤K≤100000, 钻石的尺寸范围 [1,10000]
输入样例：
代码语言：javascript复制5 3
1
6
4
3
1输出样例：
代码语言：javascript复制4分析：
- 要求放入钻石差值不超过
k的条件下使得放入钻石数量最多 等价于：对于一段数列，求子序列中的任意两数之差最大不超过k的最长子序列 - 将数列排序使其单调，枚举
i为右端点，j为左端点，数组名为a - 若
a[i]与a[j]的差值大于k，则需要向右移动j，直到a[i]与a[j]的差值小于等于k
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int N=1e6 10;
int a[N];
int main(){
int n,k,ans=0;
cin>>n>>k;
for(int i=0;i<n;i ) cin>>a[i]; //读入并记录钻石尺寸
sort(a,a n); //对钻石尺寸从小到大排序
for(int i=0,j=0;i<n;i ){ //i枚举右端点
while(a[i]-a[j]>k) j ; //移动j的过程
ans=max(ans,i-j 1); //更新最长区间
}
cout<<ans<<endl;
return 0;
}
