滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

 
// 普通的queue
// push和pop的时候都会改max值
// push好处理，但是pop不好处理
 
// priority queue push自动处理
// 但是pop是按大小顺序pop的，不好处理
 
// 也就是需要最大堆的特性
// sorted_set是个合理的选择，但是不允许重复元素
// 所以使用 multiset
// 配合使用 queue，装载index，同时把index对应的value存入
 
#include<queue>
#include<set>
#include<vector>
 
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        multiset<int> value_set;
        vector<int> res;
 
        //初始化
        for(int i=0;i<k;i++){
            value_set.insert(nums[i]);
        }
        
        int max_val = *value_set.crbegin();
        res.push_back(max_val);
 
        //开始移动
        for(int j=k;j<nums.size();j++){
            //插入值
            value_set.insert(nums[j]);
            //删除值
            auto it = value_set.find(nums[j-k]);
            value_set.erase(it);
            //获取最大值
            max_val = *value_set.crbegin();
            res.push_back(max_val);
        }
        return res;
    }