c++ - 阵列最大间隙的计算

Question

我正在处理这个问题，这里有详细的问题和描述。实际上我确实搜索了一些解决方案，而且都是相似的。我的问题是，为什么只计算跨桶间隙？为什么不考虑桶内最大/最小差异？谢谢。

给定一个未排序的数组，找到其排序形式的连续元素之间的最大差异。

尝试在线性时间/空间中解决。

如果数组包含的元素少于 2 个，则返回 0。

您可以假设数组中的所有元素都是非负整数并且在 32 位有符号整数范围内。

int maximumGap(vector<int>& nums) {
        const int n = nums.size();
        if(n<=1) return 0;
        int maxE = *max_element(nums.begin(),nums.end());
        int minE = *min_element(nums.begin(),nums.end());
        double len = double(maxE-minE)/double(n-1);
        vector<int> maxA(n,INT_MIN);
        vector<int> minA(n,INT_MAX);
        for(int i=0; i<n; i++) {
            int index = (nums[i]-minE)/len;
            maxA[index] = max(maxA[index],nums[i]);
            minA[index] = min(minA[index],nums[i]);
        }
        int gap = 0, prev = maxA[0];
        for(int i=1; i<n; i++) {
            if(minA[i]==INT_MAX) continue;
            gap = max(gap,minA[i]-prev);
            prev = maxA[i];
        }
        return gap;
}

Answer 1

你有 n 个元素，你想把它们放在给定的区间内。假设区间长度为 L。G 的可能值是多少？两个连续元素之间的最大差距？显然 G 不可能大于 L，而且 G 也不能小于 L/n-1。 G 将等于 L/n-1 当且仅当我们将所有元素精确地 L/n-1 分开(即所有元素彼此距离相等)。

现在，由于这条规则，如果您创建大小正好为 L/n-1 的桶，我们有两个选择 - 所有元素彼此之间的距离相等，因此答案是 L/n-1，或者答案大于L/n-1。如果答案大于 L/n-1，则不可能在同一个桶中找到两个元素(因为每个桶的长度都是 L/n-1 ) 这就是为什么我们只考虑 桶之间的距离。

为了避免考虑两种情况，我通常让水桶在左端关闭，在右端打开。也就是说最左边的点包含在桶中，最右边的点包含在下一个桶中。最后一个桶由一个点组成——区间的末端。