LeetCode239 滑动窗口最大值

发表于 | 分类于 |
字数统计: 709 | 阅读时长 ≈ 3

链接: https://leetcode-cn.com/problems/sliding-window-maximum/

题意

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

解法

由于需要求出滑动窗口的最大值，假设当前的滑动窗口中有下标$i$和$j$且满足$ i \leq j $，且前者小于后者
当窗口向右滑动时，只要$ i $还在窗口中，则$ j $一定也在窗口中，且$ nums[i] $一定不会是窗口的最大值
因此可以把$ nums[i] $永久移除
考虑单调队列，队列中的元素按由大到小递减进行维护，每次队列头则是当前窗口的maxValue
每次添加新元素的时候把队列尾部比当前元素小的元素进行pop，始终保持队列有序
实现的时候有两种写法，一种是队列中保存数组值，另一种是存下标
实现起来差不多，存数组值的时候注意要严格小于才进行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
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        int n = nums.size();
        // 单调队列
        for (int i = 0; i < n; i++) {
            if (i >= k && dq.front() == nums[i - k]) {
                dq.pop_front();
            }
            while(dq.size() && dq.back() < nums[i]) {
                dq.pop_back();
            }
            dq.push_back(nums[i]);
            if (i >= k - 1) {
                ans.push_back(dq.front());
            }
        }
        return ans;
    }
};
// [-7,-8,7,5,7,1,6,0]
// 4

分块

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
class Solution {
public:
    vector<int> l, r, belong, val;
    int query(int x, int y, vector<int>& nums) {
        int ans = INT_MIN;
        if(belong[x] == belong[y]) {
            for (int i = x; i <= y; i++) {
                ans = max(ans, nums[i]);
            }
            return ans;
        }
        for (int i = x; i <= r[belong[x]]; i++) {
            ans = max(ans, nums[i]);
        }
        for (int i = belong[x] + 1; i < belong[y]; i++) {
            ans = max(ans, val[i]);
        }
        for (int i = l[belong[y]]; i <= y; i++) {
            ans = max(ans, nums[i]);
        }
        return ans;
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        if (n == 0) return {};
        int block = sqrt(n), num = n / block; // 块大小和块数
        if (n % block) num++;
        belong.resize(n);
        l.resize(num);
        r.resize(num);
        val.resize(num);
        for (int i = 0; i < n; i++) {
            belong[i] = i / block;
        }
        for (int i = 0; i < num; i++) {
            l[i] = i * block;
            r[i] =  (i + 1) * block - 1;
        }
        r[num - 1] = n - 1;
        for (int i = 0; i < n; i++) {
            val[belong[i]] = max(val[belong[i]], nums[i]);
        }
        vector<int> ans;
        for (int i = 0; i <= n - k; i++) {
            ans.push_back(query(i, i + k - 1, nums));
        }
        return ans;
    }
};