单调队列,从大到小放
新增值小于back,加入back
大于back,删除比它小的值,.再加入
大于所有值,删除所有,把新增放首位
首位插入ans
class Solution {
public:
vector<int> maxInWindows(vector<int>& nums, int k) {
vector<int> ans;
deque<int> que;
int n = nums.size();//前排避雷 size()是O(n)的时间复杂度
for(int i=0;i<n;i++){
if(que.size() && i-k+1 > que.front())
que.pop_front();
while( que.size() && nums[i] >= nums[que.back()])
que.pop_back();
que.push_back(i);
if( i+1-k >= 0 )
ans.push_back(nums[que.front()]);
}
return ans;
}
};