牛牛分数组题解

牛牛面前有一堆数，他想把这些数分成两堆，只不过牛牛是一个很有想法的人。
他希望分得的两堆数能够满足，第一堆数的最大值和第二堆数的最小值差值最小。
由于数太多，牛牛犯了难，所以他想请你帮帮他，给定n个数，返回符合牛牛希望的分法中最小的差值是多少。

我们可以想一个贪心策略，考虑如何分才能使第一堆数的最大值和第二堆数的最小值差值最小，我们可以进行一个从小到大的排序，然后遍历这个数组，找到差值最小的相邻的数，那么这两个相邻的数作为一个分界点，刚好区分了这两堆数，这个最小的差值也是符合牛牛希望的分法中最小的差值。
将上述思想，模拟实现，代码如下：
时间复杂度
空间复杂度

class Solution {
public:
    const int inf = 0x3f3f3f3f;

    /**
     * 返回符合牛牛希望的分法中最小的差值是多少
     * @param n int整型 代表共有多少数
     * @param a int整型vector 代表每个数的大小
     * @return int整型
     */
    int solve(int n, vector<int> &a)
    {
        // write code here
        int ans = inf;
        sort(a.begin(), a.end());
        for (int i = 1; i < n; i++)
            ans = min(ans, a[i] - a[i - 1]);
        return ans;
    }
};