牛客对应题目链接：空调遥控 (nowcoder.com)

---

一、分析题目

1、滑动窗口

先排序，然后维护窗口内最大值与最小值的差在 2 * p 之间（max - min）。

---

2、二分查找

先排序，然后枚举所有的温度，⼆分出符合要求的学生区间，然后统计个数。

---

二、代码

1、滑动窗口（推荐）

//值得学习的代码
//O(NlogN)
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, p;
int arr[N];

int main()
{
    cin >> n >> p;
    for(int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);
 
    int ret = 0, left = 0, right = 0;
    p *= 2;
 
    while(right < n)
    {
        while(arr[right] - arr[left] > p)
        {
            left++;
        }
        ret = max(ret, right - left + 1);
        right++;
    }
 
    cout << ret << endl;
 
    return 0;
}

---

2、二分查找

#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e6+10;
int a[N];

int main()
{
    int n, p;
    cin >> n >> p;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a+n);
    int res=0;
    int mini=a[0], maxi=a[n-1];
    for(int k=mini; k<=maxi; k++)
    {
        int target=max(k-p, 1);
        int left=0, right=n-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(a[mid]>=target) right=mid;
            else left=mid+1;
        }
        int l=left;
        
        left=0, right=n-1;
        target=k+p;
        while(left<right)
        {
            int mid=left+(right-left+1)/2;
            if(a[mid]<=target) left=mid;
            else right=mid-1;
        }
        res=max(res, right-l+1);
    }
    cout << res << endl;
    return 0;
}

---

三、反思与改进

我只想到了暴力解法，显示排序，然后确定 K 的范围是在数组 a 中的最大和最小值之间，接着看看有多少学生符合要求。因为是取绝对值，所以我就想着从中间值开始向两边遍历，遇到不符合要求的就可以直接 break 了，然后在所有情况里面取最大值即可，但这样做肯定超过数据范围。在看有多少学生符合要求这里可以进行优化，利用二分来确定符合要求学生的范围，再通过范围即可得出数量。

如果采用滑动窗口的话，这道题的核心就在于需要控制最大值与最小值的差在 2 * p 之间，这个点没有想到。