HackerRank MAXMIN问题解决方案超时，求优化方法

你的当前解决方案超时的核心原因是两层嵌套循环，时间复杂度达到了O(n²)，当处理大输入数组时，这种复杂度会导致运行时间超出限制。不过好在我们可以利用数组排序后的特性来大幅优化效率。

优化思路 #

因为你已经对数组进行了排序，那么最小的"不公平值"（即子数组中最大值和最小值的差）一定出现在连续的k个元素中。为什么？因为排序后数组是递增的，任何非连续的k个元素的差值只会更大。比如，如果你选了第i个和第i+k个元素，它们的差值肯定比第i个到第i+k-1个的差值大。

基于这个思路，我们只需要遍历一次数组，计算每一组连续k个元素的差值，然后记录最小的那个即可，这样时间复杂度就降到了O(n log n)（主要来自排序操作，遍历是O(n)）。

修正后的代码 #

import java.util.Arrays;

public class Solution { 
    // Complete the maxMin function below.
    static int maxMin(int k, int[] arr) {
        Arrays.sort(arr);
        int unfair = Integer.MAX_VALUE;
        // 只需要遍历到arr.length - k的位置，避免数组越界
        for(int i = 0; i <= arr.length - k; i++){
            int diff = arr[i + k - 1] - arr[i];
            if(diff < unfair){
                unfair = diff;
            }
        }
        return unfair;
    }
}

代码解释 #

1. 排序数组：和你原来的操作一样，先把数组按递增顺序排列。
2. 单次遍历计算差值：从第0个元素开始，每次取当前元素和之后第k-1个元素的差值（因为数组排序，后者是这k个元素里的最大值）。
3. 更新最小不公平值：每次计算出的差值如果比当前记录的最小值小，就更新最小值。
4. 循环边界：循环到arr.length - k就停止，这样i + k -1不会超出数组的最后一个索引。

用你给出的示例输入7 3 10 100 300 200 1000 20 30来测试：
排序后的数组是[10,20,30,100,200,300,1000]，k=3。计算每一组连续3个元素的差值：

• 10,20,30 → 30-10=20
• 20,30,100 →100-20=80
• 30,100,200 →200-30=170
• ... 后面的差值更大
  所以最小的差值是20，和示例输出一致。

内容的提问来源于stack exchange，提问作者saadhq20