[LeetCode]Sliding Window Maximum

O(n * log n)的解法显而易见，用priority_queue即可。但是很显然，即使用了优先队列，我们还是包含了很多的重复计算，比如数组[0,3,1,2,4,-1,0]，window size为3。那么当我们遍历到4的时候，我们之前在priority_queue里维护的所有东西都可以不要了，因为他们都没有4大，而且过期更早，无论如何他们都不会是之后任何一个window的最大值了。假设我们用stack来存，每次我们pop所有比当前数curr小的元素，然后push curr，这样我们可以排除我们不需要考虑的元素，并且这个栈是单调递减的。新加的元素我们已经处理完毕，接下来我们应该考虑如何处理过期的元素。如果过期的元素就是最大值，很简单我们remove stack最底下的元素，因为他是最大的。但是因为我们要从stack底层remove元素，再用stack就不行了，但是我们又要支持在末尾进行删除操作，所以queue也不行。这里我们需要用double-ended queue，其支持O(1)的首位插入和删除元素的操作，完美符合我们的需求。如果过期的不是最大值，事实上我们我们没有必要一定要现在将其从dequeue上去除，因为对于结果不影响，我们只需要在remove dequeue首位元素(原stack最底层，也就是最大值)时，一口气把所有之后成为dequeue首位元素仍然过期的元素去除即可，这样对之后的结果也不会产生影响。整体算法如下：

• 将所有dequeue末尾小于等于当前元素curr的数pop out，再插入curr
• 如果dequeu首位元素过期，将其remove，重复此操作直到首位元素不过期
• dequeue首位元素即为window maximum

时间复杂度和空间复杂度都是O(n)，因为所有元素只在dequeue上进出一次。代码如下：

	class Solution {
	public:
	vector<int> maxSlidingWindow(vector<int>& nums, int k) {
	int len = nums.size();
	deque<int> dq;
	vector<int> res;
	for(int i = 0; i < len; ++i)
	{
	while(dq.size() && nums[dq.back()] <= nums[i])
	dq.pop_back();
	dq.push_back(i);
	while(dq.size() && dq.front() <= i - k)
	dq.pop_front();
	if(i >= k - 1 && k)
	res.push_back(nums[dq.front()]);
	}
	return res;
	}
	};

view raw Sliding Window Maximum.cpp hosted with ❤ by GitHub