LeetCode 239. 滑动窗口最大值（滑动窗口）

题目：239. 滑动窗口最大值

思路：用一个双端队列来保存滑动窗口内的值按大到小排序，时间复杂度0(n)。细节看注释

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    	//元素值是nums的下标，满足nums值按大到小排序
        deque<int> de;
        vector<int> v;
        for(int i=0;i<nums.size();i++){
        	//保存递减的顺序
            while(de.size()&&nums[de.back()]<=nums[i]){
                de.pop_back();
            }
            de.push_back(i);
            //遍历过的元素>=k个
            if(i>=k-1){
            	//这里的while改成if也可以,因为每次最多只有一个超过滑动窗口的范围
                while(de.size()&&i-de.front()>k-1){
                    de.pop_front();
                }
                v.push_back(nums[de.front()]);
            }
        }
        return v;
    }
};