滑动窗口之滑动窗口最大值

力扣https://leetcode-cn.com/problems/sliding-window-maximum/

• 首先相同题目的比较，字符串和子字符串的相关题目是需要自己利用left、right指针来表示一个自适应的窗口，但是滑动窗口的最大值是不需要设置left、right指针的，直接设置了窗口的大小。所以在代码实现中直接利用if 先把窗口大小k-1进行 赋值，然后else进入窗口的滑动；
•  实现单调队列实现在窗口内以O(1)的复杂度获取窗口中的队列
• 「单调队列」数据结构解决滑动窗口问题

 利用单调队列作为窗口的实现，不断地压入元素到队列中，对头元素始终是最大值。

单调队列主要是解决push、pop的实现，以及实现获取队列中的max函数。

此处单调队列就是队列中的元素是呈降序排列的，每新添加进来一个元素，都会把它前面比它小的元素删除，从而保证队列的首元素是队列中最大值。

力扣https://leetcode-cn.com/problems/sliding-window-maximum/solution/dan-diao-dui-lie-by-labuladong/

class deque {
    // 在队头插入元素 n
    void push_front(int n);
    // 在队尾插入元素 n
    void push_back(int n);
    // 在队头删除元素
    void pop_front();
    // 在队尾删除元素
    void pop_back();
    // 返回队头元素
    int front();
    // 返回队尾元素
    int back();
}

 

完整代码实现

 注意单调队列的设计中push函数不能用等号，因为不然会把重复的大的值删除

 [-7,-8,7,5,7,1,6,0]  k=4

输出会编成[7,7,7,6,6]

而正解是[7,7,7,7,7]

class Solution {
public:

    vector maxSlidingWindow(vector& nums, int k) {
        vector res;
        MonotonicQueue window;
        int i=0;
        while(i monotonicQueue;
    void push(int n){//关键的push函数怎么把要插入的比它笑的元素干掉
        while(!monotonicQueue.empty()&&monotonicQueue.back()