砖石收藏家

奶牛贝茜非常喜欢闪闪发光的东西，她会在业余时间开采钻石。

她收藏了 N 颗大小不等的钻石，她想将其中的一些摆放在牛棚的展示柜当中。

为了使展示柜中的钻石尺寸大小相似，她不会将两颗尺寸大小相差超过 K 的钻石同时放在柜子中（刚好相差 K，则没有问题）。

给定 K，请帮助贝茜计算在展示柜中最多可以摆放多少颗钻石。

输入格式

第一行包含两个整数 N,K。

接下来 N 行，每行包含一个整数，表示一颗钻石的尺寸。

输出格式

输出贝茜可以在展示柜中展示的钻石最大数量。

数据范围 1≤N≤1000, 0≤K≤10000, 钻石的尺寸范围 [1,10000] 输入样例：

5 3

1

6

4

3

1

输出样例：

4

方法一：双指针法

*//用l代替左端点，r为右端点，找到最大的cnt*

using namespace std;
const int N = 1010;
int res[N];

int main()
{
    int n,k;
    cin>>n>>k;
    int ans=0,maxt=0,cnt;
    for(int i=0;i<n;i++) cin>>res[i]; //读入数据
    sort(res,res+n);
    for(int l=0,r=0;r<n;r++) {
        if(res[r]-res[l]<=k) cnt = r-l+1;  //记录长度
        else l++;
        maxt = max(cnt,maxt);  //最大长度更新
    }
    cout<<maxt;
    return 0;

}

方法二：前缀和解法

#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int s[N], f[N];

int main()
{
    int n, k, m;
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        scanf("%d", &m);
        f[m]++;
    }
    for (int i = 1; i <= 100010; i++)
        s[i] = s[i - 1] + f[i];
    int ma = -10;
    for (int i = 1; i <= 100010; i++)
        ma = max(ma, s[k + i] - s[i - 1]);
    cout << ma;
    return 0;
}