Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums = <code>[1,3,-1,-3,5,3,6,7]</code>, and k = 3.
| Window position | Max |
|---|---|
| [1 3 -1] -3 5 3 6 7 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 7 |
Therefore, return the max sliding window as <code>[3,3,5,5,6,7]</code>.
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
解题思路
这题受到求滑动窗口中位数的思想启发，可以使用有效元素概念。使用一个hash表保存被剔除的无效元素。然后使用最大堆去求窗口内的最大值，只要保证堆顶部的元素一定是有效的就可以了。
代码
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
unordered_map<int, int> hash;
priority_queue<int, vector<int>> heap;
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
if (i < k) {
heap.push(nums[i]);
} else {
res.push_back(heap.top());
heap.push(nums[i]);
hash[nums[i - k]] ++;
while (!heap.empty() && hash[heap.top()]) {
hash[heap.top()]--;
heap.pop();
}
}
}
if (!heap.empty()) {
res.push_back(heap.top());
}
return res;
}
};
当然，本题还有一种正解，那就是使用单调栈。单调栈，顾名思义，就是单调递增或者单调递减的栈。单调栈有很多应用，我们主要介绍在这里的应用。
首先，我们需要明白：
当取一个大小为k的值时，排在k前面的比k小的元素都不可能成为滑动窗口中的最大值。
由此，我们可以维护一个单调递减的单调栈：
Step1 : 判断栈底是否需要被弹出（即元素已经无效）
Step2 ：对于每一个进栈的元素，去除栈顶每一个比他小的元素，再将其入栈
Step3 ：栈底的元素值即为当前窗口的最大值
由于我们的栈比较特殊，需要在栈底和栈顶操作，所以我们使用双端队列来实现：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> ans;
for (int i=0; i<nums.size(); i++) {
if (!dq.empty() && dq.front() == i-k) dq.pop_front();
while (!dq.empty() && nums[dq.back()] < nums[i])
dq.pop_back();
dq.push_back(i);
if (i>=k-1) ans.push_back(nums[dq.front()]);
}
return ans;
}
};
