数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序查找每个大小为k的连续子数组的最大值
假设我们有一个包含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的末尾
- 当Qi不为空且arr[i] >= arr[Qi的最后一个元素]时，执行：
- 对于i < arr的大小，更新（i加1），执行：
- 显示arr[Qi的第一个元素]
- 当Qi不为空且Qi的第一个元素 <= i - k时，执行：
- 从Qi删除第一个元素
- 当Qi不为空且arr[i] >= arr[Qi的最后一个元素]时，执行：
- 从Qi删除最后一个元素
- 将i插入到Qi的末尾
- 显示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;
}
输入
{3,4,6,2,8}, 3输出
6 6 8
更新于： 2021年10月7日
366 次浏览
广告