最小化数组中相邻元素之间的最大差值

---

在这个问题中，我们将通过从数组中移除任何 M 个元素来最小化相邻元素之间的最大差值。

解决该问题的朴素方法是从数组中选择总共 N − M 个数组元素，并检查哪个集合包含最小或最大相邻差值。优化的解决方案使用队列数据结构来解决该问题。

问题陈述：我们给定一个按升序排序的数字数组。我们也给定了 M。我们需要从数组中移除 M 个元素，以便最小化相邻数组元素之间的最大差值。

示例

输入

nums = {5, 9, 12, 13, 14, 19}, M = 3

输出

 1

解释：我们可以从数组中移除 5、9 和 19。因此，相邻数组元素之间最大差值的最小值为 1。

输入

nums = {8, 9, 12, 13, 17}, M = 2

输出

3

解释：我们可以移除 8 和 17 以最小化最大相邻差值。

输入

nums = {8, 9, 10, 11, 12, 13}, K = 1

输出

1

解释：我们可以移除任何 3 个元素，因为所有元素之间的相邻差值都相同。

方法 1

在这里，我们将使用蛮力方法来解决问题。从数组中，我们可以创建 2N 个集合。之后，我们检查每个 N − K 元素集合的最大相邻差值，并将它们中的最小值作为答案。

算法

步骤 1 - 使用最大整数值初始化 'min_diff' 值。

步骤 2 - 使用 for 循环进行 2N 次迭代。

步骤 3 - 接下来，使用 __builtin_popcount() 方法查找 'p'（当前索引）中设置位的数量，并将其存储在 'cnt' 方法中。

步骤 4 - 如果 'cnt' 等于 N − K，请执行以下步骤。

步骤 4.1 - 初始化 'tmp' 列表以存储数组元素。

步骤 4.2 - 开始遍历数组。如果当前位在索引 'p' 中是设置位，则将元素插入到 'tmp' 列表中。

步骤 4.3 - 使用最小整数值初始化 max_diff。

步骤 4.4 - 遍历数组元素并找到最大相邻差值。

步骤 4.5 - 之后，如果 min_diff 大于 max_diff，则更新 min_diff。

步骤 5 - 返回 min_diff 值。

示例

#include <bits/stdc++.h>
using namespace std;

int minimumDiff(vector<int> nums, int len, int M) {
    // Minimum difference
    int min_diff = INT_MAX;
    // Traverse for 2^N subsets
    for (int p = 0; p < (1 << len); p++) {
        // Number of array elements to be considered in the given set. It gives the number of 1 in the binary string
        int cnt = __builtin_popcount(p);
        // When len - M elements are left in the set
        if (cnt == len - M) {
            // temporary array
            vector<int> tmp;
            for (int q = 0; q < len; q++) {
                if ((p & (1 << q)) != 0)
                    tmp.push_back(nums[q]);
            }
            // To store the maximum difference of adjacent elements
            int max_diff = INT_MIN;
            for (int q = 0; q < tmp.size() - 1; q++) {
                max_diff = max(max_diff,  tmp[q + 1] - tmp[q]);
            }
            min_diff = min(min_diff, max_diff);
        }
    }
    return min_diff;
}

int main() {
    int M = 3;
    vector<int> nums = {5, 9, 12, 13, 14, 19};
    int len = nums.size();
    cout << "The minimum of maximum difference between adjacent elements is " << minimumDiff(nums, len, M);
    return 0;
}

输出

The minimum of maximum difference between adjacent elements is 1

时间复杂度 - O(N*2N)，其中 O(N) 用于遍历数组，O(2N) 用于检查数组的每个子集。

空间复杂度 - O(N − M) 用于存储数组元素。

方法 2

我们可以观察到，从数组中间移除数组元素总是会增加数组元素之间的差值，因为数组按升序排序。因此，我们总是需要从数组的两端移除数组元素。

例如，数组为 [2, 5, 7, 9, 10]。如果我们移除 9，它会增加 7 和 10 之间的差值。因此，从两端移除数组元素是一个好主意。

为了解决这个问题，我们将数组中相邻元素的差值存储起来。之后，我们将遍历大小为 N − K 的每个子数组，并使用滑动窗口技术获取所有子数组中最大相邻差值的最小值。

算法

步骤 1 - 遍历数组并将下一个元素和当前元素之间的差值存储在 nums_diff[p] 中。

步骤 2 - 执行 findMinimum() 函数以查找每个子数组中的最小差值。

步骤 3 - 在 findMinimum() 函数中，创建一个大小为 k 的双端队列以存储数组元素的索引。

步骤 4 - 使用循环处理第一个窗口。如果队列不为空，并且队列最后一个索引处的元素大于当前元素，则从队列中移除该元素。此外，使用 while 循环移除所有大于当前元素的元素。

步骤 5 - 将当前元素插入到队列中。

步骤 6 - 现在，我们需要处理其他窗口。因此，使用最大整数值初始化 min_diff 并开始遍历其他窗口。

步骤 7 - 如果 ind_que.front() 索引处的元素小于 min_diff，则更新 min_diff 变量的值。

步骤 8 - 使用循环，从队列中移除前一个窗口的索引。

步骤 9 - 移除小于当前元素的元素的索引，并将当前元素插入到队列中。

步骤 10 - 处理最后一个窗口的 min_diff 值并从函数中返回它。

示例

#include <bits/stdc++.h>
using namespace std;

int findMinium(vector<int> arr, int n, int k) {
    // Deque to store array indexes
    deque<int> ind_que(k);
    int p;
    // Handle the first window
    for (p = 0; p < k; ++p) {
        // Remove smaller elements from the back of queue
        while ((!ind_que.empty()) && arr[p] >= arr[ind_que.back()])
            ind_que.pop_back(); // Remove last element
        // Add curent index to queue
        ind_que.push_back(p);
    }
    int min_diff = INT_MAX;
    // Handle other windows
    for (; p < n; ++p) {
        // The first element is largest in deque
        min_diff = min(min_diff, arr[ind_que.front()]);
        // Update the current window
        while ((!ind_que.empty()) && ind_que.front() <= p - k)
            ind_que.pop_front();
        // Remove smaller elements than current element
        while ((!ind_que.empty()) && arr[p] >= arr[ind_que.back()])
            ind_que.pop_back();
        // Push current element
        ind_que.push_back(p);
    }
    // Handle the last window
    min_diff = min(min_diff, arr[ind_que.front()]);
    return min_diff;
}
int minimumDiff(vector<int> nums, int len, int M) {
    // Difference array
    vector<int> nums_diff(len - 1);
    for (int p = 0; p < len - 1; p++) {
        nums_diff[p] = nums[p + 1] - nums[p];
    }
    return findMinium(nums_diff, len - 1, len - M - 1);
}
int main() {
    int M = 2;
    vector<int> nums = {8, 9, 12, 13, 17};
    int len = nums.size();
    cout << "The minimum of maximum difference between adjacent elements is " << minimumDiff(nums, len, M);
    return 0;
}

输出

The minimum of maximum difference between adjacent elements is 3

时间复杂度 - O(N)

空间复杂度 - O(N) 用于将差值存储到队列中。

我们使用双端队列数据结构，因为我们可以在双端队列的两端执行插入和删除操作。程序员可以尝试使用不同的数据结构（如数组）来解决此问题。