题目描述

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

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

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

样例

算法1

(暴力枚举) $O(n*k)$

C++ 代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        for(int left=0, right = left+k-1; right<nums.size(); ++left, right = left+k-1){

            int val = INT_MIN;
            for(int i=left; i<=right; ++i){
                val = max(val,nums[i]);
            }
            res.push_back(val);
        }
        return res;
    }
};

超出时间限制

算法2

(单调队列) $O(n)$

抄的，用来记录学习。没找yxc题解链接

维护一个单调队列，队列长度为3，（最多包含nums3个位置上的数），单调递减。
当i之前，que已经包含3个元素位置，表明队列已满，需要弹出对头元素；在压入队列之前，需要保持队列单调属性；最后压入i。

C++ 代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> st;

        for(int i=0; i<nums.size(); ++i){
            if(!st.empty() && i-k+1 > st.front()) st.pop_front();
            while(!st.empty() && nums[i] >= nums[st.back()]) st.pop_back(); 
            st.push_back(i);
            if(i >= k-1) res.push_back(nums[st.front()]); 
        }
        return res;

    }
};