刷题

滑动窗口的最大值

scorlw 发布于

滑动窗口的最大值

关键词：滑动窗口最值、deque

题目描述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入: 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

解法

解法一：

思路：

  • 这种滑动窗口的最值问题，一般可以考虑使用队列或者栈来对最值进行保存。
  • 当新加入的值比队列末尾的值大时，则pop掉队列尾部的值，一直到可以保证新队列是递减的（可能包含相等的值）。

算法流程：

  1. 判断nums 的size以及k值等，增强函数的鲁棒性；
  2. 建立队列，用来保存最值；
  3. 首先根据第一个窗口的值来初始化队列；
  4. 之后根据窗口的移动，判断是否pop当前的队首值以及保证队列的递减性。

代码：

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
class Solution {
public:
    deque<int> dq;
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        if(n <= 0) return {};
        vector<int> res;
        
        for(int i = 0;i<k;i++){
                //单调减
                while(dq.size() && nums[i] > dq.back()) dq.pop_back();//当队列中有元素时，pop_back出所有比nums[i]小的数
                dq.push_back(nums[i]);
        }
        res.push_back(dq.front());
        for(int i = k;i<n;i++){

            //先删除nums[i-k]之后添加nums[i]，若是先添加则会破坏dq的原有结构，造成错误

            //若是窗口划过的元素nums[i-k]刚好为dq的首节点，即最大值时 将dq头删去
            if(dq.front()==nums[i-k])
                dq.pop_front();
            //维护单调性
            while(dq.size()&&nums[i]>dq.back()) dq.pop_back();
            //个数不能大于k，我感觉不加也可以
            if(dq.size()==k) dq.pop_back();
            dq.push_back(nums[i]);
            res.push_back(dq.front());
        }
        return res;
    }
};

带有IO的代码：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
    vector<int> res;
    if(k > nums.size() || nums.size() <= 0 || k <= 0) return res;
    deque<int> dq;
    dq.push_back(nums[0]);
    for(int i = 1; i < k; i++){
        while(dq.size() && nums[i] > dq.back()) dq.pop_back();
        dq.push_back(nums[i]);
    }
    res.push_back(dq.front());
    for(int i = k; i < nums.size(); i++){
        if(dq.front() == nums[i-k])
            dq.pop_front();
        while (dq.size() && nums[i] > dq.back()) dq.pop_back();
        dq.push_back(nums[i]);
        res.push_back(dq.front());        
    }
    return res;
}

int main()
{
    vector<int> nums;
    {//对于输入的代码，可以使用大括号括起来，输入结束后直接释放局部变量
        int a;
        while(cin >> a){
            nums.push_back(a);
            if(cin.get() == '\n') break;//注意位置，需要放在后面，否则读不到最后一个数据
        }
        for(int i : nums){
            cout << i << " ";
        }
        cout << endl;
    }
    int k;
    cin >> k;
    for(int a : maxSlidingWindow(nums, k))
    {
        cout << a << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}

知识点

  1. 队列deque