Luobuyu's Blog

0%

239.滑动窗口最大值

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.2k 阅读时长 ≈ 1 分钟
滑动窗口模板。

239.滑动窗口最大值

题目描述：

给出一个整数数组 $nums$ ，有一个大小为 $k$ 的滑动窗口从最左侧移动到最右侧。返回滑动窗口中的最大值。

数据范围：
$1\le n \le 10^5, 1\le k \le n$

题解：

使用单调队列，单调队列需要使用双端队列。因为求最大值，所以维护一个单调减的队列，里面放元素的下标。

当前要加入第 $i$ 个元素，加入之后的情形为 $(q[hh], \cdots,i)$ ，此时队列的大小为 $i - q[hh] + 1$ ，如果 $i - q[hh] + 1 > k$ ，说明加入之后超过了窗口大小，所以在加入之前需要弹出队首过期元素。也可以判断当前容量是不是已经达到了 $k$ ，即 $q[tt] - q[hh] + 1 \ge k$ 。

1
while(tt >= hh && q[tt] - q[hh] + 1 >= k) ++hh;

同时对待加入的元素 $nums[i]$ 需要维护单调性，和队尾元素比较，如果队尾元素小则一直弹出队尾。

1
while(tt >= hh && nums[i] >= nums[q[tt]]) --tt;

然后才能加入 $i$ 到队列

1
q[++tt] = i;

使用数组实现双端队列，其中初始值 $hh = 0, tt = -1$ ，保证了 $q[hh],q[tt]$ 分别表示队首队尾。

代码：

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
class Solution
{
public:
    const static int maxn = 1e5 + 1;
    static void optimize_cpp_stdio() { ios::sync_with_stdio(false), cin.tie(0); }
    int q[maxn];
    int hh = 0, tt = -1;
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        optimize_cpp_stdio();
        vector<int> ans;
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            // 判断窗口大小，移出队首
            while (tt >= hh && q[tt] - q[hh] + 1 >= k) // 写成 i - q[hh] + 1 > k 或者 i - q[hh] >= k 会更快一点
                hh++;
            // 判断单调减
            while (tt >= hh && nums[i] >= nums[q[tt]])
                --tt;
            q[++tt] = i;
            if (i + 1 >= k)
                ans.emplace_back(nums[q[hh]]);
        }
        nums.clear();
        return ans;
    }
};