思路
直接暴力法，发现超时，怎么进一步优化呢？每个窗口我们都要从头到尾扫描一遍来寻找最大值，这是耗时所在，因为是寻找最大值，直接想到一种非常适合的数据结构——大根堆，堆顶就是最大值。每往右移动一次，就将新的元素加入堆中，再判断堆顶元素是否在窗口内，如果不是就移除，直到在当前窗口的元素成为堆顶。因为将一个元素加入到堆中的时间复杂度为$O(log n)$，所以算法的时间复杂度为$O(n log n)$。
能不能进一步优化呢？当然可以，在一个窗口中，假设两个元素的下标分别为$i, j$且$i < j$，那么「只要$i$在窗口中，$j$也必定在窗口中」。若$nums[i] < nums[j]$， 那么$nums[i]$必定不可能成为最大值，我们就可以不必存储类似$nums[i]$的值。所以，我们只需要用一个双端队列来存储「在当前窗口中可能在以后成为最大值的值的对应下标」。存储下标是因为我们后续要判断该值是否超过窗口范围。
根据前面的分析可知，该队列中的元素是递增的（因为是从左往后扫描的），元素(下标)对应的值是递减的。每次移动窗口就只需要将新元素与队尾元素对应的值进行比较，如果队尾元素对应的值小于新加元素对应的值，则将其移除（因为其对应的值不可能成为最大值了），不断地进行此项操作，直到队列为空或者新元素对应的值小于队尾元素对应值。
显然，队首元素对应的值就是当前窗口的最大值，但需要注意队首元素是否超过了窗口的范围。
这样我们只需要$O(n)$时间内就能完成此题。
代码
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
| class Solution
{
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
deque<int> dq;
// 初始化, 即处理第一个窗口中的值
for (int i = 0; i < k; ++i)
{
// 将不可能成为最大值的移除队列
while (!dq.empty() && nums[dq.back()] < nums[i])
{
dq.pop_back();
}
dq.push_back(i);
}
vector<int> ans = { nums[dq.front()] };
for (int i = 1; i <= (nums.size() - k); ++i)
{
// 将不可能成为最大值的移除队列
while (!dq.empty() && nums[dq.back()] < nums[i + k - 1])
{
dq.pop_back();
}
dq.push_back(i + k - 1);
// 将超过窗口范围的元素移除队列
while (!dq.empty() && dq.front() < i)
{
dq.pop_front();
}
ans.push_back(nums[dq.front()]);
}
return ans;
}
};
|
zyz