题目
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 = [1,3,-1,-3,5,3,6,7], 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 [3,3,5,5,6,7].
思路
又是《剑指Offer》的原题（#65），大致讲一下思路吧。
思路来源于之前做过的一道题，是要求设计一个栈，可以用O(1)时间找到栈中最大(最小)元素的。当时的方法是，另辟一个栈，记录可能会改变最大值的那些值（可以称他们为关键值），当这弹出的栈顶元素恰好是这些值的时候，把关键值栈顶的元素也弹出。这就相当于做了“撤销”操作，这时关键值栈顶的新元素也就是目前的最大值了。
假设我们用一个容器存放那些可能成为最大值的元素，那维护它过程就发生在向后移动窗口读入一个新元素a[i]时，主要的想法有两步：
- 如果a[i]比容器中那些排在它前面的（先前读入的）元素大，由于a[i]的存活时间肯定比老一辈们来的长，因此前面那些比它的值还小的元素就可以删去了；
- 删去那些“过气”的元素，也就是目前已经不在窗口中的那些元素；
每挪动一下，可以得知当前窗口最大的元素肯定就是在容器最前头的（可能是还没“过气”老大），后面排着一串老大挂掉后想当老大的元素
由于按照时间顺序，“过气”元素在容器的开头，而我们又要从容器的末尾开始找那些比a[i]小的元素，因此有这么两个重要决定：
- 使用双端队列存放候选元素：因为我们要方便地操作数组的首末项；
- 队列中存放元素的序号而不是值：这是因为我们要判断哪些元素已经滑出窗口了，如果存储值的话，每次还得重新到原序列里找位置；
整个方法的时间复杂度是O(n)，空间复杂度应该也是O(n)
代码
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int numSz = nums.size();
vector<int> results;
if(numSz <= 0 || k > numSz){
return results;
}
deque<int> working;
//Init deque
for(int i=0; i<k; i++){
while(!working.empty() && nums[i]>=nums[working.back()]){
working.pop_back();
}
working.push_back(i);
}
results.push_back(nums[working.front()]);
//Interate through remaining nums
for(int i=k; i<numSz; i++){
while(!working.empty() && working.front() <= (i-k)){
working.pop_front(); //Remove the out-of-window elements
}
while(!working.empty() && (nums[i]>=nums[working.back()])){
working.pop_back(); //Remove the smaller elements
}
working.push_back(i);
results.push_back(nums[working.front()]);
}
return results;
}
};