Mutiset-(剑指offer-面试题65)滑动窗口

太过爱你忘了你带给我的痛 2022-05-17 02:11 145阅读 0赞

*  # Multiset-(剑指offer-面试题65)滑动窗口 #

--------------------

*  ## 题目链接：[7:滑动窗口][7] ##
 *  ## 简讲Multiset： ##

multiset是set的一个分支，在set的基础上**允许重复键值‘**

和set一样自带**升序排序**，查找和删除

*  ## 思路： ##

选用multiset的原因很粗暴，因为要求的是窗口的最大和最小值，set自带排序，***又不能保证窗口的值唯一***

这种题目最怕超时，如果每次窗口移动都完整进行一次窗口填满就有点浪费时间

multi自带查找和删除，**窗口移动实际上就是把原窗口最左的元素扔掉，再加入最靠近原窗口右边一个元素**

不过有点要注意，erase()支持两种参数，迭代器指针和数据a，如果是参数是数据a会把multiset中所有a都删除，不可

所以**用迭代器指针作为参数**，指针怎么来？**用find()查找数据，find()会返回第一个查找的迭代器指针**

*  ## 代码： ##

#include<iostream>
    #include<set>
    using namespace std;
    #define MAX_Size 1000005
    //数据结构与算法Mooc（第三章栈与队列7窗口移动）
    int main()
    {
    	multiset<int> Windows;
    	int Data[MAX_Size];
    	int MAX_List[MAX_Size];
    	int MIN_List[MAX_Size];
    	int Length, Window_Length;
    	cin >> Length >> Window_Length;
    	int Num = Length - Window_Length + 1;	//计算窗口总数
    	for (int i = 0; i < Length; i++)
    	{
    		cin >> Data[i];
    		if (i < Window_Length)		//窗口数据进入
    			Windows.insert(Data[i]);
    	}
    
    	for (int i = 0; i < Num; i++)
    	{
    		if (i)		//窗口移动时
    		{
    			auto it = Windows.find(Data[i-1]);		//查找移动前最左的元素，删除
    			Windows.erase(it);
    			Windows.insert(Data[i + Window_Length-1]);	//窗口向右移动加入数据
    		}
    		auto it = Windows.begin();		//set自动升序排序，begin为窗口最小值，end-1为最大值
    		MIN_List[i] = *it;
    		it = Windows.end();
    		it--;				//end-1才是窗口尾部数据
    		MAX_List[i] = *it;
    	}
    	for (int i = 0; i < Num; i++)
    		cout << MIN_List[i] << " ";
    	cout << endl;
    	for (int i = 0; i < Num; i++)
    		cout << MAX_List[i] << " ";
    	cout << endl;
    
    
    	return 0;
    
    }

[7]: http://dsalgo.openjudge.cn/stackqueue/7/