C++ 程序用于查找每个 k 大小连续子数组的最大值

c++server side programmingprogramming

假设我们有一个包含 n 个元素且值为 k 的数组。我们必须为每个大小为 k 的连续子数组找到最大值。

因此，如果输入为 arr = [3,4,6,2,8], k = 3，则输出将是大小为 3 的连续子数组为 [3,4,6], [4,6,2], [6,2,8]，因此最大元素为 6、6 和 8。

为了解决这个问题，我们将遵循以下步骤 −

定义一个大小为 k 的双端队列 Qi
初始化 i := 0，当 i < k，更新(将 i 增加 1)，执行:
- 当 Qi 不为空且 arr[i] >= arr[Qi 的最后一个元素] 时，执行:
  - 从 Qi 中删除最后一个元素
- 将 i 插入 Qi 末尾
对于 i < arr 的大小，更新(将 i 增加 1)，执行以下操作:
- 显示 arr[Qi 的第一个元素]
- 当 Qi 不为空且 Qi 的第一个元素 <= i - k 时，执行以下操作:
  - 从 Qi 中删除前一个元素
- 当 Qi 不为空且 arr[i] >= arr[Qi 的最后一个元素] 时，执行以下操作:
  - 从 Qi 中删除最后一个元素
- 在 Qi 末尾插入 i
显示 arr[Qi 的第一个元素]

示例

让我们看看下面的实现以便更好地理解 −

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main(){
   vector<int> arr = {3,4,6,2,8};
   int k = 3;
   deque<int> Qi(k);
   int i;
   for (i = 0; i < k; ++i){
      while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
         Qi.pop_back();

         Qi.push_back(i);
     }
     for ( ; i < arr.size(); ++i){
        cout << arr[Qi.front()] << " ";
        while ( (!Qi.empty()) && Qi.front() <= i - k)
            Qi.pop_front();
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
            Qi.pop_back();
        Qi.push_back(i);
    }
    cout << arr[Qi.front()] << endl;
}