数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究最小化数组中相邻元素之间的最大差值
在这个问题中，我们将通过从数组中移除任何 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) 用于将差值存储到队列中。
我们使用双端队列数据结构，因为我们可以在双端队列的两端执行插入和删除操作。程序员可以尝试使用不同的数据结构（如数组）来解决此问题。
484 次浏览
