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.
解題思路
這題受到求滑動窗口中位數(shù)的思想啟發(fā)详幽，可以使用有效元素概念。使用一個hash表保存被剔除的無效元素版姑。然后使用最大堆去求窗口內(nèi)的最大值迟郎，只要保證堆頂部的元素一定是有效的就可以了。
代碼
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;
}
};
當然表制，本題還有一種正解，那就是使用單調(diào)棧控乾。單調(diào)棧么介，顧名思義蜕衡，就是單調(diào)遞增或者單調(diào)遞減的棧。單調(diào)棧有很多應(yīng)用，我們主要介紹在這里的應(yīng)用蒜绽。
首先桶现，我們需要明白：
當取一個大小為k的值時鼎姊，排在k前面的比k小的元素都不可能成為滑動窗口中的最大值。
由此相寇，我們可以維護一個單調(diào)遞減的單調(diào)棧：
Step1 : 判斷棧底是否需要被彈出（即元素已經(jīng)無效）
Step2 ：對于每一個進棧的元素，去除棧頂每一個比他小的元素唤衫，再將其入棧
Step3 ：棧底的元素值即為當前窗口的最大值
由于我們的棧比較特殊，需要在棧底和棧頂操作休里，所以我們使用雙端隊列來實現(xiàn)：
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;
}
};
