问题描述
如下图所示，长度为k的滑动窗口在数组中从左往右移动，求出在移动过程中，窗口中的最大值的集合。(窗口的长度不长于数组长度)
初步解法——使用优先队列
考虑示例中的nums[1]，显然可知的是，nums[1]作为最大值的有效窗口只能是区间[0, 2]和[1, 3]，一旦某个时刻的窗口起始位置大于了最大值x的位置，那么x就不再有效了。
由于最大值的判定和位置十分相关，所以我们在记录最大值的时候，也很有必要将它的位置一并记录下来，如下所示：
1
| using Pir = pair<int, int>;
|
接下来就是思考有哪些数据结构可以在低于线性复杂度的情况下找到最值。优先队列就是其中的一种。重点来了，本题适合选用优先队列的原因就在于：对于固定的一个最值x，其服务的窗口区间仅仅是离他最近的那些区间。倘若在某一个时刻我们发现，当前的窗口区间对于最值x已经不再有效，那么对于之后时刻的窗口区间更加不会有效。故之前将其舍弃即可。
讲到这里，优先队列的解法也就很明了了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
using Pir = pair<int, int>;
priority_queue<Pir> Q;
vector<int> ans;
auto len = static_cast<int>(nums.size());
for(int i = 0; i < k; ++i){
Q.push({nums[i], i});
}
ans.emplace_back(Q.top().first);
for(int i = k; i < len; ++i){
Q.push({nums[i], i});
while(Q.top().second <= i-k){
Q.pop();
}
ans.emplace_back(Q.top().first);
}
return ans;
}
};
|
优化解法——基于双端队列的单调队列解法
显然，我们可以得到这样一个断言：
对于窗口区间[i, i+k)中的某个位置t，如果nums[t] > nums[t-s], s>=1，那么毫无疑问，在位置t之前的元素都不可能再成为窗口的最大值了。
根据这个断言，我们很容易做出判断：对于断言中那些不可能成为窗口最大值的元素，应该将其舍弃。实施了这样的舍弃原则之后，对于保留下来的元素，则必定满足：nums[pre] > nums[pos], pre < pos。即：
如果我们使用一个双端队列来存储元素，则该队列一定满足降序
另外，由于是降序的形式，所以在进行舍弃的时候，应该从队列的末端进行依次舍弃(因为要从小到大进行比较嘛)，这也是为什么需要双端队列的原因。
最后，由于需要满足最大值服务区间的限制，所以对于超出有效区间范围的元素，则从队列的头部进行舍弃。
最后的实现如下：
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:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
using Pir = pair<int, int>;
auto len = static_cast<int>(nums.size());
if(!len) return {};
deque<Pir> DQ;
vector<int> ans;
for(int i = 0; i < k; ++i){
while(!DQ.empty() && DQ.back().first<nums[i]){
DQ.pop_back();
}
DQ.emplace_back(nums[i], i);
}
ans.emplace_back(DQ.front().first);
for(int i = k; i < len; ++i){
while(!DQ.empty() && DQ.front().second <= i-k){
DQ.pop_front();
}
while(!DQ.empty() && DQ.back().first<nums[i]){
DQ.pop_back();
}
DQ.emplace_back(nums[i], i);
ans.emplace_back(DQ.front().first);
}
return ans;
}
};
|
