算法力扣刷题三十二【239. 滑动窗口最大值】

前言

栈和队列篇。
记录三十二【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]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

二、尝试实现

思路

（1）滑动窗口的移动像是队列，移动一次：push进去一个，同时pop出去一个。想到设置queue，但是如何找出最大值？

只和队列的back元素比较？不行。
定义一个max，记录k大小窗口内的最大值，但是：除了第一个窗口可以，后面窗口，怎么把max交到第二大（下一棒）呢？该怎么记录？
又不能把窗口内k个元素排序再放入队列，这样pop不正确。

没能实现。

三、参考思路

参考思路链接

学习内容

（1）思路是一致的，可是单调队列如何实现？单调队列：pop();push();getMaxValue()。常规queue不行，需要自定义。单调队列中pop；push；getMax，都需要重新定义，不去改变窗口内元素顺序，而是把可能成为最大值的元素放到单调队列的出口。
（2）单调队列模拟过程（对应自定义pop、push、getMaxValue函数实现）

窗口移动过程中，判断窗口新囊括的元素：
- 如果单调队列里前面所有元素都比它小，push新囊括的元素同时pop队列现存所有元素，把前面比新push的元素小的都带走。让最大值占据队列出口。
- 如果单调队列里前面元素都比它大的，那么直接push即可。
- 如果单调队列里前面元素有比它大，也有比它小：把小的元素全部去掉，只留下前面比push元素大的。
- 所以单调队列的结构用deque，双向队列。方便操作。

代码实现

学习完单调队列实现思路，完成代码。

class Solution {
public:
class dq{
public:
    deque<int> dq;
    void pop(int val){
        if(!dq.empty() && val == dq.front()){
            dq.pop_front();
        }
    }
    void push(int val){
        while(!dq.empty() && val > dq.back()){ //把所有比val小的元素都从尾巴pop出去
            dq.pop_back();
        }
        dq.push_back(val);
    }
    int getMax(){
        return dq.front();
    }
};
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;//返回值
        if(k == 1){
            return nums;
        }

        dq que;//定义dq对象
        for(int i = 0;i < k  ;i++){//第一个窗口。
            que.push(nums[i]);
        }
        result.push_back(que.getMax());
        for(int j = k;j < nums.size();j++){ //移动窗口
            que.pop(nums[j-k]);
            que.push(nums[j]);
            result.push_back(que.getMax());
        }
        return result;
    }
};