力扣第1984题精解：如何通过排序将时间复杂度优化到O(n log n)？

题目解读

给定一个整数数组和一个整数 k，需要找到所有大小为 k 的子数组中最大值与最小值的差值的最小值。例如，数组 [9,4,1,7] 中若 k=2，则子数组有 [9,4]（差为5）、[4,1]（差为3）、[1,7]（差为6），最终结果为3。题目要求通过排序和窗口滑动的思路，高效计算这一最小差值。

解题思路与过程

核心思路是通过排序简化差值计算，具体步骤如下：

1‌.降序排序数组‌：使用自定义比较函数 comp 将数组从大到小排序。降序排列后，每个连续的 k 元素的窗口中，第一个元素是窗口内的最大值，最后一个元素是最小值。

2‌.滑动窗口遍历‌：遍历所有可能的窗口（共 n - k + 1 个），计算当前窗口首尾元素的差值（即最大值与最小值的差），并记录全局最小差值。

3‌.特殊处理 k=1‌：此时所有子数组的差值为0，直接返回。

该算法的时间复杂度主要由排序决定（O(n log n)），空间复杂度为 O(n)。通过排序将差值计算简化为首尾元素之差，避免了每个窗口重新遍历查找极值。

代码：

bool comp(int a, int b) { return a > b; }  // 自定义降序排序规则  

class Solution {  
public:  
    int minimumDifference(vector<int>& nums, int k) {  
        if (k == 1) {  // 特殊处理：k=1时差值为0  
            return 0;  
        }  
        int n = nums.size();  
        int newnums[1000];  // 声明临时数组（隐含长度限制）  
        for (int i = 0; i < n; i++) {  
            newnums[i] = nums[i];  // 复制原数组到临时数组  
        }  
        sort(newnums, newnums + n, comp);  // 降序排序  
        int minmum = 100001;  // 初始化为极大值  
        // 滑动窗口遍历所有k长度子数组  
        for (int i = 0; i < n - k + 1; i++) {  
            // 计算当前窗口首尾差值，并更新最小值  
            minmum = min(newnums[i] - newnums[i + k - 1], minmum);  
        }  
        return minmum;  
    }  
};