239. Sliding Window Maximum

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;	}};