滑动窗口最大值

---

20190505171747817.gif

map法（很笨）

利用map红黑树的有序及删除

class Solution {
public:
    map<int,int>m;
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>res;
        if(k>nums.size()){
            return res;
        }

        for(int i=0;i<k;i++){
            if(m.count(nums[i])==0){
                m[nums[i]]=1;
            }
            else{
                m[nums[i]]++;
            }                
        }
        res.push_back((--m.end())->first);
        for(int i=k;i<nums.size();i++){
            if(m.count(nums[i])==0){
                m[nums[i]]=1;
            }else{
                m[nums[i]]++;
            }
            if(m[nums[i-k]]==1){
                m.erase(nums[i-k]);
            }
            else{
                m[nums[i-k]]--;
            }
            res.push_back((--m.end())->first);
        }
        return res;
    }
};

单调队列

（1）如何得到最优解？

<1> 保证窗口中的最大值始终在窗口的最左端。while 将窗口中所有小于或等于当前新加入元素的元素移出，将当前元素加入窗口；

（2）如何保证最优质在有效期内？

<2> while 如果窗口最左端的元素的下标超出窗口的范围，则将其移出窗口；
<3> 每个时刻窗口中的元素最大值都在窗口的最左端，也就是头部，可以直接输出。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>res;
        list<pair<int,int>>list;
        if(k>nums.size()){
            return res;
        }
        int j;
        list.push_back(make_pair(nums[0],0));
        for(int i = 1; i < k;i++){
            while(!list.empty()&&list.back().first<nums[i]){
                list.pop_back();
            }          
            list.push_back(make_pair(nums[i],i));  
        }
        res.push_back(list.begin()->first);
        for(int i = k; i < nums.size();i++){
            j=i-(k-1);
            while(!list.empty()&&list.back().first<nums[i]){
                list.pop_back();
            }
            list.push_back(make_pair(nums[i],i));
            while(!list.empty()&&list.begin()->second<j){
                list.pop_front();
            }
            res.push_back(list.begin()->first);
        }
        return res;
    }
};