隊列的最大值

隊列的最大值

題目1：滑動窗口的最大值。給定一個數組和滑動窗口的大小，請找出所有滑動窗口裡的最大值。比如，給定數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3,那麼滑動窗口的最大值為{4,4,6,6,6,5}。

思路：假設index是一個兩端開口的隊列，用來保存有可能是滑動窗口最大值的數字的下標。在存入一個數字之前，首先需要判斷隊列里已有數字是否小於待存入的數字。

2. 如果隊列的頭部數字已經從窗口裡滑出，那麼滑出的數字也需要從隊列的頭部刪除。

參考代碼：

root@gt:/home/git/Code# ./a.out 4 4 6 6 6 5 root@gt:/home/git/Code# cat maxwindows.cpp #include <iostream>#include <vector>#include <deque>using namespace std;vector<int> maxinwindows(vector<int>& num,int size){ vector<int> max; if(num.size() >= size && size > 0) { 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.push_back(num[index.front()]); while(!index.empty() && num[i] >= num[index.back()]) index.pop_back(); while(!index.empty() && index.front() <= (int)(i - size)) index.pop_front(); index.push_back(i); } max.push_back(num[index.front()]); } return max;}int main(){ int temp[] = {2,3,4,2,6,2,5,1}; vector<int> num(temp,temp + sizeof(temp)/sizeof(int)); vector<int> res = maxinwindows(num,3); for(vector<int>::iterator it = res.begin();it != res.end();++it) cout << *(it) << " "; cout << endl; return 0;}

推薦閱讀：