题解 | #滑动窗口中位数#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return double浮点型vector
     
     */vector<double> slidewindow(vector <int>& nums, int k) {
        int n=nums.size();//找到初始数组个数
         vector<double>arr;//创建记录结果数组
         multiset<int>st;//创建multiset数组
        int left=0;//int一个左边界
        for(int i=0;i<k;i++)st.insert(nums[i]);//先往multset插入几个数字
         auto mid=next(st.begin(),k/2);//定义一个中位数
         if(k%2!=0)arr.push_back(*mid);//如果k是奇数插入答案中间数字
             else 
             {
                 arr.push_back((*mid+*prev(mid))/2.0);//如果K是偶数插入答案中间左右数的平均数mid为靠右数
             }
         for(int right=k;right<n;right++)
         {
             st.insert(nums[right]);//往multset插入新数字，长度为k+1
             if(nums[right]<*mid)mid--;//如果新插的数字小于原来的mid，往左移mid（不用担心k为奇数插入后mid靠左）
             if(nums[left]<=*mid)mid++;//如果左指针小于mid往右移
             st.erase(st.find(nums[left]));//删除左指针所指的，平衡长度k
             left++;左指针右移
             if(k%2!=0)arr.push_back(*mid);//插入答案
             else 
             {
                 arr.push_back((*mid+*prev(mid))/2.0);
             }
         }
         return arr;// write code here
    }
    
};