大小为 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] - min_ele = −2, max_ele = 6 -> min_ele + max_ele = 4

  • [5, −2, 6, 4] - min_ele = −2, max_ele = 6 -> min_ele + max_ele = 4

  • [−2, 6, 4, 8] - min_ele = −2, max_ele = 8 -> min_ele + max_ele = 6

  • [6, 4, 8, −9] - min_ele = −9, max_ele = 8 -> min_ele + max_ele = −1

  • [4, 8, −9, 10] - min_ele = −9, max_ele = 10 -> min_ele + max_ele = 1

  • [8, −9, 10, −5} - min_ele = −9, max_ele = 10 -> min_ele + max_ele = 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 - 开始遍历给定数组，并使用 'm' 变量初始化为 0 来跟踪子数组的长度。另外，使用 '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'。

示例

Open Compiler
#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() 索引处的元素大于第 p 个索引处的元素。

步骤 4.2 - 同样，如果数组中 dec.back() 索引处的元素小于第 p 个索引处的元素，则从 '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' 值。

示例

Open Compiler
#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)，在双端队列中存储索引。

第二种方法在时间复杂度方面更加优化。但是，它比第一种方法占用更多空间。程序员可以根据给定的元素数量使用任何方法。对于较小的输入，第一种方法适用，而对于较大的输入，第二种方法适用。

更新于: 2023-07-22

453 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告