題目描述
給定一個陣列和滑動視窗的大小，找出所有滑動視窗里數值的最大值，例如，如果輸入陣列{2,3,4,2,6,2,5,1}及滑動視窗的大小3，那么一共存在6個滑動視窗，他們的最大值分別為{4,4,6,6,6,5}； 針對陣列{2,3,4,2,6,2,5,1}的滑動視窗有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}， 思路：利用雙端佇列來構建一個單調佇列，對頭放置當前視窗的最大值，代碼如下：class Solution {public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { deque<int> dep; vector<int> rev; for(int i=0;i<num.size();i++) { while(dep.size()&&num[dep.back()]<=num[i]) { dep.pop_back(); } if(dep.size()&&(i-dep.front()+1)>size) dep.pop_front(); dep.push_back(i); if(size&&i+1>=size) rev.push_back(num[dep.front()]); } return rev; }};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/3836.html
標籤：其他
上一篇：剪繩子
下一篇：【最新】經典面試100問，附答案