原题链接
题目描述：有一个ab的整数组成的矩阵，现请你从中找出一个nn的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入格式：第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。 100%的数据2<=a,b<=1000,n<=a,n<=b,n<=1000
输出格式：仅一个整数，为ab矩阵中所有“nn正方形区域中的最大整数和最小整数的差值”的最小值。
输入样例： 5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2
输出样例： 1
解析：题意十分简单，像是个二维的RMQ（可我不会打...）。 想到选取的范围是有限的，像是在移动一个固定的框，于是就往单调队列上想了想。 好像真的可以用单调队列做，做两次，一次维护横着的k个中的最值，一次维护竖着的k个中的最值。 最大值和最小者各做一次，这题就做完了？
代码如下：
#include<cstdio> #include<algorithm> using namespace std; const int maxn = 1005; int n, m, k, a[maxn][maxn], f[maxn][maxn], g[maxn][maxn], maxv[maxn][maxn], minv[maxn][maxn], ans; int que[maxn], tail, head; int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } int main() { n = read(); m = read(); k = read(); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) a[i][j] = read(); for (int i = 1; i <= n; ++ i) { //维护横行的最大值 head = tail = 0; que[0] = 0; for (int j = 1; j <= m; ++ j) { if (a[i][j] <= a[i][que[tail - 1]]) que[tail ++] = j; else { while (a[i][j] > a[i][que[tail - 1]] && tail > head) tail --; que[tail ++] = j; } while (que[tail - 1] - que[head] + 1 > k) head ++; if (j >= k) f[i][j - k + 1] = a[i][que[head]]; } } for (int j = 1; j <= m; ++ j) { //维护竖行的最大值 head = tail = 0; que[0] = 0; for (int i = 1; i <= n; ++ i) { if (f[i][j] <= f[que[tail - 1]][j]) que[tail ++] = i; else { while (f[i][j] > f[que[tail - 1]][j] && tail > head) tail --; que[tail ++] = i; } while (que[tail - 1] - que[head] + 1 > k) head ++; if (i >= k) maxv[i - k + 1][j] = f[que[head]][j]; } } for (int i = 1; i <= n; ++ i) { //维护横行的最小值 head = tail = 0; que[0] = 0; for (int j = 1; j <= m; ++ j) { if (a[i][j] >= a[i][que[tail - 1]]) que[tail ++] = j; else { while (a[i][j] < a[i][que[tail - 1]] && tail > head) tail --; que[tail ++] = j; } while (que[tail - 1] - que[head] + 1 > k) head ++; if (j >= k) g[i][j - k + 1] = a[i][que[head]]; } } for (int j = 1; j <= m; ++ j) { //维护竖行的最小值 head = tail = 0; que[0] = 0; for (int i = 1; i <= n; ++ i) { if (g[i][j] >= g[que[tail - 1]][j]) que[tail ++] = i; else { while (g[i][j] < g[que[tail - 1]][j] && tail > head) tail --; que[tail ++] = i; } while (que[tail - 1] - que[head] + 1 > k) head ++; if (i >= k) minv[i - k + 1][j] = g[que[head]][j]; } } ans = 2e9; for (int i = 1; i <= n - k + 1; ++ i) for (int j = 1; j <= m - k + 1; ++ j) ans = min(ans, maxv[i][j] - minv[i][j]); printf("%d", ans); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10205746.html
相关资源：JAVA上百实例源码以及开源项目