java最大子矩阵

男娘i 2024-03-26 13:17 66阅读 0赞

问题描述  
小明有一个大小为  
�  
×  
�  
N×M 的矩阵, 可以理解为一个  
�  
N 行  
�  
M 列的二维数组。

## 我们定义一个矩阵   �   m 的稳定度   �   (   �   )   f(m) 为   �   (   �   ) ##

max  
⁡  
(  
�  
)  
−  
min  
⁡  
(  
�  
)  
f(m)=max(m)−min(m), 其中  
max  
⁡  
(  
�  
)  
max(m) 表示矩阵  
�  
m 中的最大值,  
min  
⁡  
(  
�  
)  
min(m) 表示矩阵  
�  
m 中的最小值。

现在小明想要从这个矩阵中找到一个稳定度不大于 limit 的子矩阵, 同时他还希望这个子矩阵的面积越大越好 (面积可以理解为矩阵中元素个数)。

子矩阵定义如下: 从原矩阵中选择一组连续的行和一组连续的列, 这些行列交点上的元素组成的矩阵即为一个子矩阵。

输入格式  
第一行输入两个整数  
�  
,  
�  
N,M, 表示矩阵的大小。

接下来  
�  
N 行, 侮行输入  
�  
M 个整数，表示这个矩阵。

最后一行输入一个整数 limit, 表示限制。

辎出格式  
输出一个整数. 分别表示小明选择的子矩阵的最大面积。

样例输入  
3 4  
2 0 7 9  
0 6 9 7  
8 4 6 4  
8  
copy  
样例输出  
6  
copy  
样例说明  
满足稳定度不大于 8 的且面积最大的子矩阵总共有三个, 他们的面积都是 6 (粗体表示子矩阵元素)

2 0 7 9

0 6 9 7

8 4 6 4

2 0 7 9

0 6 9 7

8 4 6 4

2 0 7 9

0 6 9 7

8 4 6 4

评测用例规模与约定  
图片描述

对于所有评测用例,  
0  
≤  
0≤ 矩阵元素值, limit  
≤  
1  
0  
5  
≤10  
5  
。

运行限制  
最大运行时间：5s  
最大运行内存: 512M

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.StreamTokenizer;
    //1:无需package
    //2: 类名必须Main, 不可修改
    
    public class Main {
        
    	final static int N = 85;
    	final static int M = (int) 1e5 + 10;
    	static int n, m, k;
    	static int g[][]; // 矩阵
    	// 滑动窗口的最大值最小值
    	static int maxn[][];
    	static int minn[][];
    	static int maxnn[][];
    	static int minnn[][];
    
    	static int q[];// 维护最小值所在位置
    	static int q1[];// 维护最大值所在位置
    	static int hh, tt, hh1, tt1;
    
    	static int max(int a, int b) {
        
    		return a > b ? a : b;
    	}
    
    	static int min(int a, int b) {
        
    		return a > b ? b : a;
    	}
    
    	// 判断大小为x*y的子矩阵是否满足条件
    	static boolean check(int x, int y) {
        
    
    		for (int i = 1; i <= n; i++) {
        
    			hh = hh1 = 0;
    			tt = tt1 = 0;
    			for (int j = 1; j <= m; j++) {
        
    				while (hh < tt & q[hh] <= j - y)
    					hh++;
    				while (hh1 < tt1 && q1[hh1] <= j - y)
    					hh++;
    				while (hh < tt && g[i][q[tt1 - 1]] > g[i][j])
    					tt--;
    				while (hh1 < tt1 && g[i][q1[tt1 - 1]] < g[i][j])
    					tt1--;
    				q[tt++] = j;
    				q1[tt1++] = j;
    				maxn[i][j] = g[i][q1[hh1]];
    				minn[i][j] = g[i][q[hh]];
    			}
    		}
    		for (int i = 1; i <= m; i++) {
        
    			hh = hh1 = 0;
    			tt = tt1 = 0;
    			for (int j = 1; j <= n; j++) {
        
    				while (hh < tt & q[hh] <= j - x)
    					hh++;
    				while (hh1 < tt1 && q1[hh1] <= j - x)
    					hh1++;
    				while (hh < tt && minn[q[tt - 1]][i] > minn[j][i])
    					tt--;
    				while (hh1 < tt1 && maxn[q1[tt1 - 1]][i] < maxn[j][i])
    					tt1--;
    				q[tt++] = j;
    				q1[tt1++] = j;
    				maxnn[j][i] = maxn[q1[hh1]][i];
    				minnn[j][i] = minn[q[hh]][i];
    			}
    		}
    		for (int i = x; i <= n; i++)
    			for (int j = y; j <= m; j++)
    				if (maxnn[i][j] - minnn[i][j] <= k) {
        
    					return true;
    				}
    		if (maxnn[n][m] - minnn[n][m] <= k)
    			return true;
    		return false;
    	}
    
    	static int get_max(int x) {
        
    		int l = 0, r = m;
    		int mid;
    		while (l < r) {
        
    			mid = l + r + 1 >> 1;
    			if (check(x, mid))
    				l = mid;
    			else
    				r = mid - 1;
    		}
    		return r;
    	}
    
    	public static void main(String[] args) throws IOException {
        
    		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    //        Scanner sc = new Scanner (new BufferedInputStream(System.in));
    		in.nextToken();
    		n = (int) in.nval;// 行数
    		in.nextToken();
    		m = (int) in.nval;// 列数
    		g = new int[n + 1][m + 1];// 申请矩阵的空间大小
    		// 读进矩阵的值
    		for (int i = 1; i <= n; i++)
    			for (int j = 1; j <= m; j++) {
        
    				in.nextToken();
    				g[i][j] = (int) in.nval;
    			}
    		// 初始化
    		maxn = new int[n + 1][m + 1];
    		minn = new int[n + 1][m + 1];
    		maxnn = new int[n + 1][m + 1];
    		minnn = new int[n + 1][m + 1];
    		// 根据行值和列值大的那个来申请空间
    		q = new int[max(m + 1, n + 1)];
    		q1 = new int[max(m + 1, n + 1)];
    		in.nextToken();
    		k = (int) in.nval;
    		int ans = 0;// 最大子矩阵的面积
    		for (int i = 1; i <= n; i++)// 枚举子矩阵的行数
    			ans = max(ans, i * get_max(i));// get_max(i)在当前行下能获得最大面积的列值
    		System.out.print(ans);
    	}
    
    }