题解 | #滑动窗口的最大值#

题目主要信息：

• 要寻找每个滑动窗口的最大值，每次只滑一位
• size等于0或者大于数组长度，都返回空值

举一反三：

学习完本题的思路你可以解决双向队列或者滑动窗口的题目：

BM92.最长无重复子数组

方法一：双向队列（推荐使用）

知识点：双向队列

如果说队列是一种只允许从尾部进入，从头部出来的线性数据结构，那双向队列就是一种特殊的队列了，双向队列两边，即头部和尾部都可以进行插入元素和删除元素的操作，但是也只能插入到最尾部或者最头部，每次也只能取出头部元素或者尾部元素后才能取出里面的元素。

思路：

我们都知道，若是一个数字A进入窗口后，若是比窗口内其他数字都大，那么这个数字之前的数字都没用了，因为它们必定会比A早离开窗口，在A离开之前都争不过A，所以A在进入时依次从尾部排除掉之前的小值再进入，而每次窗口移动要弹出窗口最前面值，因此队首也需要弹出，所以我们选择双向队列。

具体做法：

• step 1：维护一个双向队列，用来存储数列的下标。
• step 2：首先检查窗口大小与数组大小。
• step 3：先遍历第一个窗口，如果即将进入队列的下标的值大于队列后方的值，依次将小于的值拿出来去掉，再加入，保证队列是递增序。

//先遍历一个窗口
for(int i = 0; i < size; i++){
    //去掉比自己先进队列的小于自己的值
    while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
        dq.pollLast();
    dq.add(i);
}

• step 4：遍历后续窗口，每次取出队首就是最大值，如果某个下标已经过了窗口，则从队列前方将其弹出。
• step 5：对于之后的窗口，重复step 3，直到数组结束。

图示：

，

Java实现代码：

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //窗口大于数组长度的时候，返回空
        if(size <= num.length && size != 0){
            //双向队列
            ArrayDeque <Integer> dq = new ArrayDeque<Integer>();  
            //先遍历一个窗口
            for(int i = 0; i < size; i++){
                //去掉比自己先进队列的小于自己的值
                while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
                     dq.pollLast();
                dq.add(i);
            }
            //遍历后续数组元素
            for(int i = size; i < num.length; i++){
                //取窗口内的最大值
                res.add(num[dq.peekFirst()]);
                while(!dq.isEmpty() && dq.peekFirst() < (i - size + 1))
                    //弹出窗口移走后的值
                    dq.pollFirst(); 
                //加入新的值前，去掉比自己先进队列的小于自己的值
                while(!dq.isEmpty() && num[dq.peekLast()] < num[i])
                    dq.pollLast();
                dq.add(i);
            }
            res.add(num[dq.pollFirst()]);
        }     
        return res;
    }
}

C++实现代码：

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        //窗口大于数组长度的时候，返回空
        if(size <= num.size() && size != 0){
            //双向队列
            deque <int> dq;  
            //先遍历一个窗口
            for(int i = 0; i < size; i++){
                //去掉比自己先进队列的小于自己的值
                while(!dq.empty() && num[dq.back()] < num[i]) 
                     dq.pop_back();
                dq.push_back(i);
            }
            //遍历后续数组元素
            for(int i = size; i < num.size(); i++){
                res.push_back(num[dq.front()]);
                while(!dq.empty() && dq.front() < (i - size + 1))
                    //弹出窗口移走后的值
                    dq.pop_front();  
                //加入新的值前，去掉比自己先进队列的小于自己的值
                while(!dq.empty() && num[dq.back()] < num[i])
                    dq.pop_back();
                dq.push_back(i);
            }
            res.push_back(num[dq.front()]);
        }     
        return res;
    }
};

Python代码实现：

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        res = []
         #窗口大于数组长度的时候，返回空
        if size <= len(num) and size != 0:
            from collections import deque
            #双向队列
            dq = deque() 
            #先遍历一个窗口 
            for i in range(size):
                #去掉比自己先进队列的小于自己的值
                while len(dq) != 0 and num[dq[-1]] < num[i]: 
                     dq.pop()
                dq.append(i)
            #遍历后续数组元素
            for i in range(size, len(num)):
                res.append(num[dq[0]])
                while len(dq) != 0 and dq[0] < (i - size + 1):
                    #弹出窗口移走后的值
                    dq.popleft()
                #加入新的值前，去掉比自己先进队列的小于自己的值  
                while len(dq) != 0 and num[dq[-1]] < num[i]:
                    dq.pop()
                dq.append(i)
            res.append(num[dq[0]])
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，数组长度为$nn$，只遍历一遍数组
• 空间复杂度：$O(m)O(m)$，窗口长度$mm$，双向队列最长时，将窗口填满

方法二：暴力法（扩展思路）

思路：

另一种更简单直观的方式，莫过于直接遍历两层：第一层为窗口起点，第二层为窗口长度，即遍历了所有的窗口的每个位置。

具体做法：

• step 1：第一次遍历数组每个位置作为窗口的起点。
• step 2：从每个起点开始遍历窗口长度，查找其中的最大值。

Java实现代码：

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //窗口大于数组长度的时候，返回空
        if(size <= num.length && size != 0) 
            //数组后面要空出窗口大小，避免越界
            for(int i = 0; i <= num.length - size; i++){
                //寻找每个窗口最大值
                int max = 0; 
                for(int j = i; j < i + size; j++){
                    if(num[j] > max)
                        max = num[j];
                }
                res.add(max);
            }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        //窗口大于数组长度的时候，返回空
        if(size <= num.size() && size != 0) 
            //数组后面要空出窗口大小，避免越界
            for(int i = 0; i <= num.size() - size; i++){
                //寻找每个窗口最大值
                int max = 0; 
                for(int j = i; j < i + size; j++){
                    if(num[j] > max)
                        max = num[j];
                }
                res.push_back(max);
            }
        return res;
    }
};

Python代码实现：

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        res = []
        #窗口大于数组长度的时候，返回空
        if size <= len(num) and size != 0:  
            #数组后面要空出窗口大小，避免越界
            for i in range (len(num) - size + 1):
                #寻找每个窗口最大值
                max = 0; 
                for j in range(i, i + size):
                    if num[j] > max:
                        max = num[j]
                res.append(max)
        return res

复杂度分析

• 时间复杂度：$O(nm)O(nm)$，其中$nn$为数组长度，$mm$为窗口长度，双层for循环
• 空间复杂度：$O(1)O(1)$，没有使用额外的辅助空间，暂存的结果res不算入空间开销