C++ 计算未排序数组排序后相邻元素的最大差值

题目描述

我们需要计算一个未排序数组在排序后，相邻元素之间的最大差值。给定一个整数数组 A 和数组的大小 n，请返回最大差值。保证数组元素个数大于等于 2 且小于等于 500。

测试样例：输入 [9,3,1,10]，大小 4，返回 6。

虽然题目通常期望 O(n) 的解法，但利用 STL 标准库中的堆排序算法是快速上手的方案。下面展示具体的 C++ 实现。

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

class MaxDivision {
public:
    int findMaxDivision(vector<int> A, int n) {
        // 构建堆并排序
        make_heap(A.begin(), A.end());
        sort_heap(A.begin(), A.end());
        
        int max = 0, i, tmp;
        for (i = 1; i < n; i++) {
            tmp = A[i] - A[i - 1];
            if (tmp > max) max = tmp;
        }
        return max;
    }
};

这段代码通过 make_heap 和 sort_heap 完成了数组的重排，随后遍历一次即可得到结果。逻辑简单直接，适合快速验证思路。