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 thek 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].
Note: You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:Could you solve it in linear time?
Hint:
How about using a data structure such as deque (double-ended queue)?The queue size need not be the same as the window’s size.Remove redundant elements and the queue should store only elements that need to be considered.
Subscribe to see which companies asked this question.
給出一個序列nums和一個窗口值k，每k個數求其中的最大值。要求線性時間復雜度。用deque來實現，用deque保存索引值，比較前面的索引值放在deque的后面，對于當前的數，與deque中的數比較。deque中比當前數還小的在當前以及以后的窗口中都不可能是最大值，所以可以pop出去。直到當前數比deque頭部的值小，然后把當前數push進去。這樣deque就是數值從小到大排序，索引從大到小排序的。為了保持子序列不超過窗口大小，如果deque的尾部索引值比下一個窗口的最左端索引要小的話，就pop出去。每個窗口的最大值就是當前deque的尾部索引值對應的序列中的值。
代碼：
class Solution{public:	vector<int> maxSlidingWindow(vector<int>& nums, int k) 	{		deque<int> window;		vector<int> res;		for(int i = 0; i < nums.size(); ++i)		{			while(!window.empty() && nums[window.front()] <= nums[i]) window.pop_front();			window.push_front(i);			if(i >= k-1) res.push_back(nums[window.back()]);			if(window.back() <= i-k+1) window.pop_back();		}		return res;	}};