AcWing 1091. 个人代码_java
原题链接
中等
作者:
季之秋
,
2021-05-07 21:55:26
,
所有人可见
,
阅读 336
import java.util.*;
public class Main{
static int N = 1010, a, b, n;
static int q[] = new int[N];
static int[][] g = new int[N][N], max = new int[N][N], min = new int[N][N], maxest = new int[N][N], minest = new int[N][N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
a = sc.nextInt(); b = sc.nextInt(); n = sc.nextInt();
for(int i = 1; i <= a; i ++)
for(int j = 1; j <= b; j ++)
g[i][j] = sc.nextInt();
for(int i = 1; i <= a; i ++) {
getcol_max(i);
getcol_min(i);
}
for(int j = n; j <= b; j ++){
getrow_max(j);
getrow_min(j);
}
int res = Integer.MAX_VALUE;
for(int i = n; i <= a; i ++)
for(int j = n; j <= b; j ++)
res = Math.min(res, maxest[i][j]-minest[i][j]);
System.out.println(res);
}
static void getcol_max(int i){
int hh = 0, tt = -1;
for(int j = 1; j <= b; j ++){
if(hh <= tt && q[hh] <= j-n) hh ++;
while(hh <= tt && g[i][q[tt]] <= g[i][j]) tt --;
q[++ tt] = j;
if(j >= n) max[i][j] = g[i][q[hh]];
}
}
static void getrow_max(int j){
int hh = 0, tt = -1;
for(int i = 1; i <= a; i ++){
if(hh <= tt && q[hh] <= i-n) hh ++;
while(hh <= tt && max[q[tt]][j] <= max[i][j]) tt --;
q[++ tt] = i;
if(i >= n) maxest[i][j] = max[q[hh]][j];
}
}
static void getcol_min(int i){
int hh = 0, tt = -1;
for(int j = 1; j <= b; j ++){
if(hh <= tt && q[hh] <= j-n) hh ++;
while(hh <= tt && g[i][q[tt]] >= g[i][j]) tt --;
q[++ tt] = j;
if(j >= n) min[i][j] = g[i][q[hh]];
}
}
static void getrow_min(int j){
int hh = 0, tt = -1;
for(int i = 1; i <= a; i ++){
if(hh <= tt && q[hh] <= i-n) hh ++;
while(hh <= tt && min[q[tt]][j] >= min[i][j]) tt --;
q[++ tt] = i;
if(i >= n) minest[i][j] = min[q[hh]][j];
}
}
}