C++(g++ 7.5.0) 解法, 执行用时: 163ms, 内存消耗: 12360K, 提交时间: 2022-08-14 00:54:40

#include<iostream>
using namespace std;
const int N = 1010;
int w[N][N], row_min[N][N], row_max[N][N];
int st[N];
int n, m, k;
void get_min(int a[], int b[], int n)  //获取最小值, 
{
    int l = 0, r = -1;
    for(int i = 1; i <= n; i++){
        while(l <= r && i - st[l] >= k)l++;
        while(l <= r && a[i] <= a[st[r]])r--;
        st[++r] = i;
        b[i] = a[st[l]];
    }
}
void get_max(int a[], int b[], int n)   //获取最大值
{
    int l = 0, r = -1;
    for(int i = 1; i <= n; i++){
        while(l <= r && i - st[l] >= k)l++;
        while(l <= r && a[i] >= a[st[r]])r--;
        st[++r] = i;
        b[i] = a[st[l]];
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &w[i][j]);
    for(int i = 1; i <= n; i++){
        get_min(w[i], row_min[i], m);
        get_max(w[i], row_max[i], m);
    }
    
    int ans = 1e9;
    int a[N], b[N], c[N];
    for(int i = k; i <= m; i++){
        for(int j = 1; j <= n; j++) a[j] = row_max[j][i];
        get_max(a, b, n);
        for(int j = 1; j <= n; j++) a[j] = row_min[j][i];
        get_min(a, c, n);
        
        for(int j = k; j <= n; j++) ans = min(ans, b[j] - c[j]);
    }
    cout << ans << endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 864ms, 内存消耗: 6136K, 提交时间: 2020-06-01 10:44:06

#include<bits/stdc++.h>
using namespace std;
struct Container
{
	deque<int> qmin;
	deque<int> qmax;
	Container():qmin(),qmax(){}
	void push(int n)
	{
		while(qmin.size()&&qmin.back()>n) qmin.pop_back();
		qmin.push_back(n);
		while(qmax.size()&&qmax.back()<n) qmax.pop_back();
		qmax.push_back(n);
	}
	void  pop(int n)
	{
		if(qmin.size()&&qmin.front()==n) qmin.pop_front();
		if(qmax.size()&&qmax.front()==n) qmax.pop_front();
	}
	int max()
	{
		return qmax.front();
	}
	int min()
	{
      return qmin.front();
	}
};
int main()
{
	int a,b,n;
	cin>>a>>b>>n;
	vector<vector<int> > mat(a,vector<int>(b));
	for(auto &v:mat)
	for(auto &i:v)
	cin>>i;
	vector<Container> Q(b);
	int ans=0x3f3f3f3f;
	for(int i=0;i<a;i++)
	{
		if(i>=n)
		for(int j=0;j<b;j++)
		Q[j].pop(mat[i-n][j]);
		for(int j=0;j<b;j++)
		Q[j].push(mat[i][j]);
		if(i<n-1) continue;
		Container C;
		for(int j=0;j<b;j++)
		{
			if(j-n>=0)
			C.pop(Q[j-n].max()),C.pop(Q[j-n].min());
			C.push(Q[j].max()),C.push(Q[j].min());
			if(j>=n-1)
			ans=min(ans,C.max()-C.min());
		}
	}
	cout<<ans<<endl;
}