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

• Z时代
• 2024-01-10
• 分类：综合

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

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

示例

让我们看看以下实现以获得更好的理解 -

#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;
}

输入

{3,4,6,2,8}, 3

6 6 8

以上是 查找每个 k 大小的连续子数组的最大值的 C++ 程序 的全部内容， 来源链接： utcz.com/z/317272.html