知识点

单调队列

multiset

思路

①维护单调队列 ②在multiset中维护整个滑动窗口的最小值。当窗口滑动时,对multiset中删除上一个元素,加入当前窗口末尾元素。不断更新答案即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    vector<int> minSlidingWindow(vector<int>& nums, int k) {
        // write code here
        multiset<int>now;

        for(int i=0;i<k;i++)now.insert(nums[i]);
        vector<int>anss;

        anss.push_back(*now.begin());
      //  cout<<*now.begin()<<endl;
        for(int i=k;i<nums.size();i++)
        {
           now.erase(now.find(nums[i-k]));
          now.insert(nums[i]);
           anss.push_back(*now.begin());
        }
        return anss;
    }
};