题目描述
- 给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值
-
例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3, 那么一共存在 6 个滑动窗口，它们的最大值分别是 {4, 4, 6, 6, 6, 5}, 如下表所示
题目解读
代码
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
class Solution {
public:
// num 数组； size窗口尺寸
vector<int> maxInWindows(const vector<int>& num, unsigned int size){
vector<int> max_in_windows;
if(num.size() >= size && size >= 1){
deque<int> index;
// 在第一个窗口内找到最大值
for(int i=0; i < size;i++){
while(!index.empty() && num[i] >= num[index.back()]){
index.pop_back();
}
index.push_back(i);
}
for(int i=size; i < num.size(); i++){
max_in_windows.push_back(num[index.front()]);
while(!index.empty() && num[i] >= num[index.back()]){
index.pop_back();
}
if(!index.empty() && index.front() <= (i-size)){
index.pop_front();
}
index.push_back(i);
}
max_in_windows.push_back(num[index.front()]);
}
return max_in_windows;
}
};
int main(){
Solution ss;
int array[] = {2, 3, 4, 2, 6, 2, 5, 1};
vector<int> num;
for(int i=0; i < 8; i++){
num.push_back(array[i]);
}
vector<int> result = ss.maxInWindows(num, 3);
for(int i=0; i < result.size(); i++){
cout<<result[i]<<" ";
}
cout<<endl;
}
总结展望
