极客笔记C++ 所有长度为K的子数组的最小元素和最大元素之和
在这个问题中，我们需要取长度为K的所有子数组的最大和最小元素，并将它们相加得到答案。
第一个解决方法是遍历所有长度为K的子数组，找到每个子数组的最小和最大元素，并将它们相加。解决这个问题的优化方法是使用双端队列数据结构。我们将在双端队列中存储子数组的最小和最大元素的索引。
问题陈述 − 我们给定一个包含N个正负整数值的数组nums[]。我们还给定一个正整数0 < K < N。我们需要求出所有长度为K的子数组的最大和最小元素之和。
示例
输入
nums[] = {3, 5, −2, 6, 4, 8, −9, 10, −5}, K = 4
输出
15
解释 - 在这里，我们给出了每个子数组的最小值和最大值。
- [3, 5, -2, 6] – 最小元素 = -2，最大元素 = 6 -> 最小元素 + 最大元素 = 4
-
[5, -2, 6, 4] – 最小元素 = -2，最大元素 = 6 -> 最小元素 + 最大元素 = 4
-
[-2, 6, 4, 8] – 最小元素 = -2，最大元素 = 8 -> 最小元素 + 最大元素 = 6
-
[6, 4, 8, -9] – 最小元素 = -9，最大元素 = 8 -> 最小元素 + 最大元素 = -1
-
[4, 8, -9, 10] – 最小元素 = -9，最大元素 = 10 -> 最小元素 + 最大元素 = 1
-
[8, -9, 10, -5} – 最小元素 = -9，最大元素 = 10 -> 最小元素 + 最大元素 = 1
所以，总和是4 + 4 + 6 + -1 + 1 + 1 = 15。
输入
nums[] = {3, 5, −2, 6, 4, 8, −9, 10, −5}, K = 9
输出
1
解释 - K等于数组的大小。所以，我们可以求给定数组的最小和最大元素的和，分别为-9和10。
输入
nums[] = {2, 7, −9}, K = 1
输出
0
说明− K的值为1。所以，我们可以将每个元素添加两次到总和中。
方法1
在这种方法中，我们将使用两个嵌套循环来获取长度为K的所有子数组，并找到子数组的最小和最大元素。然后，我们将所有子数组的最小和最大元素添加到结果变量中。
步骤
步骤1 - 初始化‘ans’为0，用来存储结果的和值。
步骤2 - 开始遍历给定的数组，并用0初始化‘m’变量来追踪子数组的长度。同时，用最小整数值初始化‘max_ele’变量和最大整数值初始化‘min_ele’变量。
步骤3 - 使用嵌套循环遍历数组从第p个索引开始。
步骤3.1 - 将‘m’的值增加1。
步骤3.2 - 使用max()函数获取nums[q]和max_ele元素中的最大值。同样地，使用min()函数获取nums[q]和min_ele元素中的最小值。
步骤3.3 - 如果m等于K，则将max_ele和min_ele的值加到‘ans’变量的值中，并使用break关键字中断嵌套循环。
步骤4 - 在函数末尾返回‘ans’。
示例
#include <bits/stdc++.h>
using namespace std;
int subArrSum(int nums[], int len, int K) {
// To store the resultant ans
int ans = 0;
// Get a subarray of size K
for (int p = 0; p < len; p++) {
int m = 0;
// For storing the minimum and maximum element of the subarray
int max_ele = INT_MIN;
int min_ele = INT_MAX;
for (int q = p; q < len; q++) {
m++;
max_ele = max(max_ele, nums[q]);
min_ele = min(min_ele, nums[q]);
// When we get a subarray of length K
if (m == K) {
ans += max_ele + min_ele;
break;
}
}
}
return ans;
}
int main() {
int nums[] = {3, 5, -2, 6, 4, 8, -9, 10, -5};
int len = sizeof(nums) / sizeof(nums[0]);
int K = 4;
cout << "The ans of minimum and maximum elements of all subarrays of size K is " << subArrSum(nums, len, K);
return 0;
}
输出
The ans of minimum and maximum elements of all subarrays of size K is 15
时间复杂度 – O(N*K)，因为我们遍历了所有长度为K的子数组。
空间复杂度 – O(1)，因为我们使用的是常数空间。
方法2
在这种方法中，我们将使用双端队列数据结构来解决问题。我们将创建两个不同的双端队列来跟踪当前子数组中最大和最小元素的索引。
步骤
步骤1 - 将‘totalSum’变量初始化为0，用于存储结果的总和。
步骤2 - 定义大小为K的‘inc’和‘dec’双端队列，用于跟踪子数组元素的索引。‘inc’双端队列将根据子数组元素的递增值存储数组元素的索引，‘dec’双端队列将根据子数组元素的递减值存储数组元素的索引。
步骤3 - 现在，将‘p’初始化为0，并且我们需要处理长度为K的第一个子数组。
步骤4 - 遍历长度为K的第一个子数组。
步骤4.1 - 在循环中，使用while循环从‘inc’双端队列中删除元素，如果队列不为空且数组中inc.back()索引处的元素大于pth索引处的元素。
步骤4.2 - 同样地，如果数组中dec.back()索引处的元素小于pth索引处的元素，则从‘dec’双端队列的尾部删除元素。
步骤4.3 - 将p推入‘inc’和‘dec’双端队列。
步骤5 - 我们需要处理其他长度为K的子数组。
步骤5.1 - 从‘inc’和‘dec’双端队列获取第一个索引值，根据它们的第一个索引从数组中获取元素值，并将它们添加到‘totalSum’值中。
步骤5.2 - 如果‘inc’和‘dec’双端队列的开头存在任何索引不在当前窗口中，则从双端队列中弹出它。
步骤5.3 - 再次按照步骤4.1和4.2处理其他子数组。
步骤5.4 - 将p推入两个双端队列中。
步骤6 - 处理最后一个窗口的最小和最大元素的总和。
步骤7 - 返回‘totalSum’值。
示例
#include <bits/stdc++.h>
using namespace std;
int subArrSum(int nums[], int len, int k){
int totalSum = 0;
// Deques to store indices of the current window in increasing and decreasing order, respectively;
deque<int> inc(k), dec(k);
// Handling the first window
int p = 0;
for (p = 0; p < k; p++){
// Remove elements which are greater than the current element
while ((!inc.empty()) && nums[inc.back()] >= nums[p])
inc.pop_back();
// Remove elements from dec deque which are smaller than the current element
while ((!dec.empty()) && nums[dec.back()] <= nums[p])
dec.pop_back(); // Remove from rear
// Add the nums[p] at last
inc.push_back(p);
dec.push_back(p);
}
// Hanlding other windows
for (; p < len; p++){
// get the first element from both the queues, and add them
totalSum += nums[inc.front()] + nums[dec.front()];
// Removing elements of the previous window
while (!inc.empty() && inc.front() <= p - k)
inc.pop_front();
while (!dec.empty() && dec.front() <= p - k)
dec.pop_front();
while ((!inc.empty()) && nums[inc.back()] >= nums[p])
inc.pop_back();
while ((!dec.empty()) && nums[dec.back()] <= nums[p])
dec.pop_back();
inc.push_back(p);
dec.push_back(p);
}
// Last window sum
totalSum += nums[inc.front()] + nums[dec.front()];
return totalSum;
}
int main() {
int nums[] = {3, 5, -2, 6, 4, 8, -9, 10, -5};
int len = sizeof(nums) / sizeof(nums[0]);
int K = 4;
cout << "The ans of minimum and maximum elements of all subarrays of size K is " << subArrSum(nums, len, K);
return 0;
}
输出
The ans of minimum and maximum elements of all subarrays of size K is 15
时间复杂度 – O(N + K)，遍历数组。
空间复杂度 – O(K)，用于在双端队列中存储索引。
第二种方法在时间复杂度方面更优化。然而，它占用的空间比第一种方法更多。根据给定的元素数量，程序员可以根据需要使用任何一种方式。对于小输入，第一种方法更合适，对于大输入，第二种方法更合适。