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].

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?

滑动窗口，求窗口内的最大值，要求o(n)的时间复杂度

建立一个窗口，窗内数字按从大到小的顺序排序，当新的数字加入窗内，如果窗口的大小大于题目要求，则窗口第一个元素出去。然后更新窗口内数字的顺序，如果比加入的数字小，移出窗口。

显然窗口要求两端都可以插入删除数据，，想了好久不知道怎么实现，看了Hint才觉得自己真的是笨死了。一个deque解决问题

还有就是为了判断究竟什么时候窗口的大小超出界限，我们用deque存储的不是数字，而是数字的下标。

AC代码

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int sum=nums.size(); vector<int> res; if(sum==0) return res; deque<int> temp; temp.push_back(0); for(int i=1; i<k; ++i) { if(nums[i]>nums[temp.front()]) { temp.clear(); temp.push_back(i); } else if(nums[i]>nums[temp.back()]) { while(nums[i]>nums[temp.back()]) temp.pop_back(); temp.push_back(i); } else temp.push_back(i); } res.push_back(nums[temp.front()]); for(int i=k;i<sum;++i) { if(i-temp.front()<k) { if(nums[i]>nums[temp.front()]) { temp.clear(); temp.push_back(i); } else if(nums[i]>nums[temp.back()]) { while(nums[i]>nums[temp.back()]) temp.pop_back(); temp.push_back(i); } else temp.push_back(i); } else { temp.pop_front(); while(!temp.empty()&&nums[i]>nums[temp.back()]) temp.pop_back(); temp.push_back(i); } res.push_back(nums[temp.front()]); } return res; } };还有明明说
You may assume k is always valid, ie: 1 ≤ k ≤ input array‘s size for non-empty array.

第一次提交就没有考虑数组为空的情况，结果。。。。。。

人与人之间的信任呢？还是我的英语不好-_-