题目描述
有一个a x b的整数组成的矩阵，现请你从中找出一个n x n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入描述:
第一行为三个整数，分别表示a,b,n的值；
第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。
输出描述:
输出仅一个整数，为axb矩阵中所有nxn正方形区域中的最大整数和最小整数的差值的最小值。
输入
5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2
输出
1
//二维单调队列模板题 #include<bits/stdc++.h> using namespace std; const int N = 1e3 + 7; struct Node { int data, pos; }qmax[N], qmin[N]; int rmin[N][N], rmax[N][N], cmin[N][N], cmax[N][N], a[N][N], n, m, r; int main() { cin >> n >> m >> r; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } for (int i = 1; i <= n; i++) { int minhead = 0, mintail = 0, maxhead = 0, maxtail = 0; for (int j = 1; j <= m; j++) { int now = a[i][j]; //维护最小值 while (minhead < mintail && qmin[mintail - 1].data > now) mintail--; qmin[mintail++] = Node{now, j}; while (minhead < mintail && qmin[minhead].pos <= j - r) minhead++; rmin[i][j] = qmin[minhead].data; //维护最大值 while (maxhead < maxtail && qmax[maxtail - 1].data < now) maxtail--; qmax[maxtail++] = Node{now, j}; while (maxhead < maxtail && qmax[maxhead].pos <= j - r) maxhead++; rmax[i][j] = qmax[maxhead].data; } } for (int j = r; j <= m; j++) { int minhead = 0, mintail = 0, maxhead = 0, maxtail = 0; for (int i = 1; i <= n; i++) { int nowmin = rmin[i][j], nowmax = rmax[i][j]; //维护最小值 while (minhead < mintail && qmin[mintail - 1].data > nowmin) mintail--; qmin[mintail++] = Node{nowmin, i}; while (minhead < mintail && qmin[minhead].pos <= i - r) minhead++; cmin[i][j] = qmin[minhead].data; //维护最大值 while (maxhead < maxtail && qmax[maxtail - 1].data < nowmax) maxtail--; qmax[maxtail++] = Node{nowmax, i}; while (maxhead < maxtail && qmax[maxhead].pos <= i - r) maxhead++; cmax[i][j] = qmax[maxhead].data; } } int ans = 0x3f3f3f3f; for (int i = r; i <= n; i++) { for (int j = r; j <= m; j++) { ans = min(ans, cmax[i][j] - cmin[i][j]); } } cout << ans << endl; return 0; }
原文链接: https://www.cnblogs.com/HighLights/p/13330751.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367637
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
