class Solution {
public:
class Myqueue // 单调队列
{
public:
deque<int>que;
// 因为只维护了队列最大值,故在pop时判断滑动窗口最前方的值与最大值是否相等,相等则pop
// 这样就保持了队列里的数值是单调从大到小的了。
void pop(int value)
{
if(!que.empty() && value == que.front())
{
que.pop_front();
}
}
// 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value)
{
while(!que.empty() && value > que.back())
{
que.pop_back();
}
que.push_back(value);
}
// 查询当前队列里最大值
int front()
{
return que.front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
Myqueue que;
vector<int>result;
for(int i = 0; i < k; i++) // 将前k个元素放进队列中
{
que.push(nums[i]);
}
result.push_back(que.front());
for(int i = k; i < nums.size(); i++)
{
que.pop(nums[i - k]);
que.push(nums[i]);
result.push_back(que.front()); // 记录对应的最大值
}
return result;
}
};
标签:队列,pop,int,que,C++,front,push,单调
From: https://www.cnblogs.com/dh2021/p/16856984.html