题解 | #在旋转过的有序数组中寻找目标值#

class Solution { public: vector maxInWindows(const vector& num, unsigned int size) { vector res;//最终返回的数组 if(size<0||size>num.size()) return res; //滑动窗口结构是一种非常重要的结构，就算是被火车撞了也不能忘 //滑动窗口结构主要用到双端队列这么一种结构 deque qmax;//定义一个维持窗口最大值的双端队列 for(int i=0;i<num.size();i++) { while(!qmax.empty()&&num[qmax.back()]<=num[i]){//当双端队列不为空时且此时末尾元素小于等于当前元素，此时应该将队列的末尾元素弹出 qmax.pop_back();//将末尾元素弹出 } qmax.push_back(i);//将i放进队列末尾 //更新队列的头，因为随着滑动窗口向右不断移动，队头值可能会过期 if(qmax.front()==i-size)//说明头已经过期了，弹出 { qmax.pop_front(); } if(i>=size-1){//说明已经形成窗口了 res.push_back(num[qmax.front()]);//将队头元素放入返回数组中 } } return res; } };