LeetCode 239 滑动窗口最大值
🟡 中等 https://leetcode.cn/problems/sliding-window-maximum/description/
因为左侧是按序淘汰的，因此使用队列来维护一个数组记录可能成为最大值的数
对于 2 1 4 这三个数，当4 进入时，2 1 就不可能成为最大值了，将 2 1 从队列中剔除。
队列维护的是候选人。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> max_q;
int left = 0;
vector<int> res;
for(int i = 0;i<nums.size();i++){
while(!max_q.empty()&&nums[max_q.back()]<=nums[i]) max_q.pop_back();
max_q.push_back(i);
if(i>=k-1){
res.push_back(nums[max_q.front()]);
if(max_q.front()==left) max_q.pop_front(); //每次入后，出时left 未必在队头。
left++;
}
}
return res;
}
};