JZ59 滑动窗口的最大值

发表于 分类于 本文字数： 584 阅读时长 ≈ 2 分钟

JZ59 滑动窗口的最大值

描述

给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度或窗口长度为0的时候，返回空。

数据范围： $1≤n≤10000$，$0≤size≤10000$，数组中每个元素的值满足 $∣val∣≤10000$

要求：空间复杂度$ O(n)$，时间复杂度 $O(n)$

示例1

1
2
输入：[2,3,4,2,6,2,5,1],3
返回值：[4,4,6,6,6,5]

示例2

1
2
输入：[9,10,9,-7,-3,8,2,-6],5
返回值：[10,10,9,8]

示例3

1
2
输入：[1,2,3,4],5
返回值：[]

题解

初见思路：整一个队列，然后实现一个统计队列中最大值的方法即可。

这种方法时间复杂度有点高，对每一个窗口都要遍历，属于是暴力解法了。大G老师给的更合适的解法是用双端队列deque，维护最大值对应的下标列表，每次从队尾移除比当前元素小的，然后再考虑队首的元素是否已经滑出窗口，最后再看一下是不是已经形成窗口了，若是形成则push一个最大值到答案数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <queue>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        if(num.size()<size) return {};
        vector<int> ans;
        for(int & i : num){
            q.push(i);
            if(q.size()==size){
                ans.push_back(findMaxValInQueue(q));
                q.pop();
            }
        }

        return ans;
    }
private:
    queue<int> q;
    int findMaxValInQueue(queue<int> q){
        int maxVal = q.front();
        while (!q.empty()) {
            if(q.front()>maxVal) maxVal = q.front();
            q.pop();
        }
        return maxVal;
    }
};

双端列表代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <deque>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> maxInWindows(vector<int>& num, int size) {
        vector<int> ans;
        if (num.empty() || size <= 0 || size > num.size()) return ans;

        deque<int> dq; // 存下标，保证单调递减

        for (int i = 0; i < num.size(); i++) {
            // 移除比当前元素小的
            while (!dq.empty() && num[dq.back()] <= num[i]) {
                dq.pop_back();
            }
            dq.push_back(i);

            // 移除滑出窗口的元素
            if (dq.front() <= i - size) {
                dq.pop_front();
            }

            // 窗口形成后加入答案
            if (i >= size - 1) {
                ans.push_back(num[dq.front()]);
            }
        }
        return ans;
    }
};