区间最值（RMQ）的几种方法（知识整理+小板子总结）

相当于总结一波，以后就从这里扒RMQ的板子

个人觉得博客的这个粘代码背景没我的黑底白字好看QAQ

代码总是越敲越熟的嘛……知识沉积的过程……

到时候改一改，传参的时候把数组名一起传进去，就能当小黑盒用了

 

法一（单调队列，O（n））：

//区间连续k个的最小 传进去下标 
    deque<int>q;
    for(int i=1;i<k;++i)
    {
    	while(!q.empty()&&high[q.back()]>high[i])q.pop_back();
    	q.push_back(i); 
    }
    for(int i=k;i<n;++i)
	{
	    while(!q.empty()&&high[q.back()]>high[i])q.pop_back();
    	    q.push_back(i); 
		ans=max(ans,high[q.front()]);
		if(q.front()<=i-k+1)q.pop_front();
	} 

法二（multiset，O（nlogn））：

这个东西和set其实没啥区别，

允许数字被重复插入，操作差不太多

//区间连续k个的最小 传进去值 
	multiset<int>q; 
	for(int i=1;i<k;++i)q.insert(high[i]);
        for(int i=k;i<n;++i)
	{
		q.insert(high[i]);
		ans=max(ans,*q.begin());
		q.erase(q.find(high[i-k+1]));
	} 

法三（ST表RMQ，预处理O（nlogn），查询O（1））：

void ST(int n)
{
	for(int i=1;i<n;++i)dp[i][0]=high[i];
	for(int j=1;(1<<j)<n;++j)
	{
		for(int i=1;i+(1<<j)-1<n;++i)
		{
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
		}
	} 
}

int RMQ(int l,int r)
{
	int k=log(r-l+1)/log(2);
	return min(dp[l][k],dp[r-(1<<k)+1][k]); 
}

ST(n); 
for(int i=1;i+k-1<n;++i)
ans=max(ans,RMQ(i,i+k-1));

法四（线段树，预处理O（nlogn），查询O（logn））

挺好写的吧，基础操作……

有前面那么优秀的几种就不写这个了QAQ