二维固定区间最值

二维固定区间最值问题

这里是区间是固定大小!

弱化题(一次优化就可以过)

强化题(两次优化才能过)

解法有,单调队列,优先队列,滑动窗口.(优先队速度稍微慢点,多两logn)

问题处理的核心思想是,把二维的东西化成一维

假如我们求n,m区间,n1,m1大小的区间的极差

首先

max_m[n][m], min_m[n][m]//记录的是,第i行,第j-m1+1到第j列的最值
for(行){
    queue<node>q; //处理一维固定长度最值问题
    for(列){
        //略
    }
}

然后我们得到了max_m和min_m,接下来只要知道i - m1 + 1到 i行的max_m和min_m的最值,相当于把各个max_m和min_m拼接到一起了

问题是如何遍历行呢?朴素的想法是直接暴力i到i+n1-1,一般的题也够用,如果要优化的话,就再来一次单调队列.

相当于处理二维化一维,一维求区间最大

朴素写法

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int v[1010][1010];
int max_m[1010][1010]; //代表i行,j-n+1到j的最大值 
int min_m[1010][1010];
struct node{
	int pos, val;
};
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int a,b,n;
	cin>>a>>b>>n;
	for(int i = 1; i <= a; i++){
		for(int j = 1; j <= b; j++){
			cin>>v[i][j];
		}
	}
	for(int i = 1; i <= a; i++){
		deque<node>q;//队首小 
		deque<node>p;//队首大 
		for(int j = 1; j <= n - 1; j++){
			while(!q.empty() && v[i][j] <= q.back().val)q.pop_back(); 
			q.push_back({j, v[i][j]});
			while(!p.empty() && v[i][j] >= p.back().val)p.pop_back();
			p.push_back({j, v[i][j]});
		}
		for(int j = n; j <= b; j++){
			while(!q.empty() && v[i][j] <= q.back().val)q.pop_back(); 
			q.push_back({j, v[i][j]});
			while(q.front().pos < j - n + 1) q.pop_front();
			while(!p.empty() && v[i][j] >= p.back().val)p.pop_back();
			p.push_back({j, v[i][j]});
			while(p.front().pos < j - n + 1) p.pop_front();
			max_m[i][j] = p.front().val;
			min_m[i][j] = q.front().val;
		}
	} 
	int ans = INT_MAX;
	for(int i = 1; i <= a - n + 1; i++){
		for(int j = n; j <= b; j++){
			int maxm = 0, minm = INT_MAX;
			for(int k = i; k <= i + n - 1; k++){
				maxm = max(maxm, max_m[k][j]);
				minm = min(minm, min_m[k][j]);
			}
			ans = min(ans, maxm - minm);
		}
	}
	cout<<ans<<endl;
	return 0;
}

两次单调队列写法,只要把朴素后半部分改成如下的就行了

int ans = INT_MAX;
for(int j = n; j <= b; j++){
	deque<node>q;//队首小 
	deque<node>p;//队首大 
	for(int i = 1; i <= n - 1; i++){
		while(!q.empty() && min_m[i][j] <= q.back().val)q.pop_back(); 
		q.push_back({i, min_m[i][j]});
		
		while(!p.empty() && max_m[i][j] >= p.back().val)p.pop_back();
		p.push_back({i, max_m[i][j]});
	}
	for(int i = n; i <= a; i++){
		while(!q.empty() && min_m[i][j] <= q.back().val)q.pop_back(); 
		q.push_back({i, min_m[i][j]});
		while(q.front().pos < i - n + 1) q.pop_front();
		
		while(!p.empty() && max_m[i][j] >= p.back().val)p.pop_back();
		p.push_back({i, max_m[i][j]});
		while(p.front().pos < i - n + 1) p.pop_front();
		ans = min(ans, p.front().val - q.front().val);
	}
}
cout<<ans<<endl;