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
| class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> maxNum;
vector<int> result;
for (int i = 0; i < nums.size(); i++)
{
if(i >= k && nums[i-k] == maxNum.front())
maxNum.pop_front();
if(maxNum.size() == 0)
maxNum.push_back(nums[i]);
else
{
while(!maxNum.empty() &&nums[i] > maxNum.back())
{
maxNum.pop_back();
}
maxNum.push_back(nums[i]);
}
if(i >= k - 1)
result.push_back(maxNum.front());
}
return result;
}
};
|
定义一个双向队列maxNum,用来储存所有可能成为滑动窗口内最大值的数。
一个数如果比另一个数“老”，而且不比这个数大，那么这个数绝无在后面的移动中成为最大值的可能。
那么我们定义的队列，一定是一个从老到新，从大到小排列的队列（因为新入队的大数会把老的小数全部淘汰）。最大值一定在队列的头。进一步可以推理出出队和入队的操作：
- 出队：如果这个数还在队列中（没被淘汰），那么就把它出队。
- 入队：入队的同时，淘汰所有的比它更小的数。
所以只需要维护这个队列，即可得到答案。
时间复杂度为\(O(n)\),空间复杂度为\(O(k)\)。