学习+刷题：239. 滑动窗口最大值

题目描述：

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
示例 2：

输入：nums = [1], k = 1
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：代码随想录上给出了单调队列的解法。

中心思想就是利用双向队列deque 写一个新函数或者在类力定义它的push  和pop 

push的时候不要直接push，先看push的这个值value是否比队列(back处)的值大，如果是，就从back处弹出，pop_back()，直到value<=que.back()。这样可以保证que.front() 的值一直是最大的。

同样弹出的时候，也要考虑此时que.front() 的值是否等于滑动窗口最左侧的值，等于的话就弹出，不等于的话说明在push那一步的时候已经弹出过了，就不用进行操作。

class Solution {
     class MyQueue
 {
public:
deque<int>dq;
void pop(int value)
{
    if(!dq.empty() && value==dq.front())
    {
        dq.pop_front();
    }
}
void push(int value)
{
    while(!dq.empty() && value>dq.back())
    {
        dq.pop_back();
    }
    dq.push_back(value);
}
int ans()
{
    return dq.front();
}
 };

public:
vector<int>maxSlidingWindow(vector<int>& nums,int k)
{
    MyQueue que;
    vector<int>res;
    for(int i=0;i<k;i++)
    {
        que.push(nums[i]);
    }
    res.push_back(que.ans());
    for(int i=k;i<nums.size();i++)
    {
        que.pop(nums[i-k]);
        que.push(nums[i]);
        res.push_back(que.ans());
    }
    return res;

    }
};