这道温度差问题的解题思路（滑动窗口版）

一开始我用暴力法写的代码，能算出结果但数据量大了会超时，后来琢磨透了滑动窗口的思路，又快又稳，分享给和我一样好久没碰算法的小伙伴～

先搞懂题目核心：把问题换个说法

题目要求找一个温度K，让最多队员满足 |a[i] - K| ≤ p。其实可以转化成：找一个长度为2p的区间（[K-p, K+p]），让数组里落在这个区间的数最多。

为啥是2p？因为区间从K-p到K+p，总长度就是 (K+p) - (K-p) = 2p 呀～

关键技巧：排序 + 滑动窗口

1. 排序的意义

把数组排序后，落在同一个区间里的数一定是连续的一段（比如区间[2,6]，排序后的数组[1,2,8,9,10]里，8、9、10就挨在一起），这是滑动窗口能生效的前提。

2. 滑动窗口怎么玩？（用简单例子说清）

举个例子：n=5，p=2（2p=4），数组是[1,2,8,9,10]（已经排好序）。我们用两个指针left（左边界）、right（右边界），像框子一样框出当前符合条件的区间：

• 初始化left=0，记录最大人数的result=0；
• right从0开始往右走：
• right=0（对应数据1）：1-1=0≤4 → 窗口长度1，result=1；
• right=1（对应数据2）：2-1=1≤4 → 窗口长度2，result=2；
• right=2（对应数据8）：8-1=7>4 → 把left往右挪（left=1），此时8-2=6还是>4 → 继续挪left（left=2），8-8=0≤4 → 窗口长度1，result还是2；
• right=3（对应数据9）：9-8=1≤4 → 窗口长度2，result还是2；
• right=4（对应数据10）：10-8=2≤4 → 窗口长度3，result=3； 最终result=3，就是最多能满足的队员数。

核心逻辑：

① right一直往右走，把新数纳入窗口；

② 只要窗口里「最右数 - 最左数 > 2p」，就把left往右挪（注意用while循环，可能要挪多次）；

③ 每次调整完，算一下当前窗口长度（right - left + 1），更新最大人数。

最终代码（带注释）

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 队员数
        int p = in.nextInt(); // 能接受的温度差
        int[] a = new int[n];
        
        // 输入队员的温度诉求
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        
        // 排序是滑动窗口的前提！
        Arrays.sort(a);
        
        int left = 0;
        int maxResult = 0; // 记录最多满足的人数
        // right指针遍历整个数组（一直往右走）
        for (int right = 0; right < n; right++) {
            // 窗口无效就收缩左指针（直到满足条件）
            while (a[right] - a[left] > 2 * p) {
                left++;
            }
            // 计算当前窗口长度，更新最大值
            maxResult = Math.max(maxResult, right - left + 1);
        }
        
        System.out.println(maxResult);
        in.close();
    }
}

最后划重点

1. 先把问题转化成「找长度2p的区间」，排序后满足条件的数必连续；
2. 滑动窗口的核心是：right扩、left缩，只遍历数组一次，效率贼高；
3. 收缩left一定要用while，别用if（不然可能缩不够而if又不会再次执行）。