是真的一点都不会

用户名：dotcpp0702741

访问量：3010

签　名：

等　　级
排　　名	3604
经　　验	1810
参赛次数	0
文章发表	25
年　　龄	0
在职情况	学生
学　　校	福建农林大学
专　　业	空间信息与数字技术

　　自我简介：

TA的其他文章

蓝桥杯2022年第十三届省赛真题-求阶乘
浏览：95

蓝桥杯2022年第十三届省赛真题-最大子矩阵
浏览：52

蓝桥杯2023年第十四届省赛真题-买瓜
浏览：229

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

蓝桥杯2022年第十三届省赛真题-最大子矩阵

　　作者: 是真的一点都不会　　　　发表时间：2024-01-20 23:21:24 浏览：52　|　评论：0　

原题链接：蓝桥杯2022年第十三届省赛真题-最大子矩阵

import java.io.IOException;
    import java.util.Deque;
    import java.util.LinkedList;
    import java.util.Scanner;
    
    public class Main {
    	private int[][][] max, min;
    	private int[][] matrix;
    	private int limit;
    
    	public void go() {
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		int m = sc.nextInt();
    		max = new int[m][n][n]; // 第m列 的i到j区间的最大值
    		min = new int[m][n][n];
    		matrix = new int[n][m];
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < m; j++) {
    				matrix[i][j] = sc.nextInt();
    			}
    		}
    		limit = sc.nextInt();
    
    		// 预处理每列从j到k这个区间内的最大最小值
    		for (int i = 0; i < m; i++) {
    			for (int j = 0; j < n; j++) {
    				for (int k = j; k < n; k++) {
    					if (k == j) {
    						max[i][j][k] = matrix[k][i];
    						min[i][j][k] = matrix[k][i];
    					} else {
    						max[i][j][k] = Math.max(matrix[k][i], max[i][j][k - 1]);
    						min[i][j][k] = Math.min(matrix[k][i], min[i][j][k - 1]);
    					}
    				}
    			}
    		}
    
    		int res = getRes();
    		System.out.print(res);
    	}
    
    	public int getRes() {
    		int n = matrix.length, m = matrix[0].length;
    		int res = 1;
    		// 遍历上下边界
    		for (int x1 = 0; x1 < n; x1++) {
    			for (int x2 = x1; x2 < n; x2++) {
    				// 双端队列枚举最大面积
    				res = Math.max(res, (x2 - x1 + 1) * longestSubarray(x1, x2));
    			}
    		}
    		return res;
    	}
    
    	public int longestSubarray(int x1, int x2) {
    		int m = matrix[0].length;
    		int res = 0, l = 0;
    		Deque<Integer> maxQueue = new LinkedList<>();
    		Deque<Integer> minQueue = new LinkedList<>();
    		for (int i = 0; i < m; i++) {
    			while (!minQueue.isEmpty() && minQueue.peekLast() > min[i][x1][x2]) {
    				minQueue.pollLast();
    			}
    			minQueue.addLast(min[i][x1][x2]);
    			while (!maxQueue.isEmpty() && maxQueue.peekLast() < max[i][x1][x2]) {
    				maxQueue.pollLast();
    			}
    			maxQueue.addLast(max[i][x1][x2]);
    
    			if (maxQueue.peek() - minQueue.peek() > limit) {
    				while (!minQueue.isEmpty() && !maxQueue.isEmpty()
    						&& maxQueue.peek() - minQueue.peek() > limit) {
    					if(min[l][x1][x2]==minQueue.peek()) {
    						minQueue.pollFirst();
    					}
    					if(max[l++][x1][x2]==maxQueue.peek()) {
    						maxQueue.pollFirst();
    					}
    				}
    				res=Math.max(res, i-l+1);
    			}
    			res=Math.max(res, i-l+1);
    		}
    		return res;
    	}
    
    	public static void main(String[] args) throws IOException {
    		new Main().go();
    	}
    }

0.0分

0 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

是真的一点都不会

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C二级辅导-进制转换（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

回文数字（C++代码）

蓝桥杯2022年第十三届省赛真题-最大子矩阵

评论区

精彩推荐

点我有惊喜！你懂得！

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

求圆的面积（C语言代码）

打水问题（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

是真的一点都不会

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C二级辅导-进制转换 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

回文数字 （C++代码）

蓝桥杯2022年第十三届省赛真题-最大子矩阵

评论区

精彩推荐

点我有惊喜！你懂得！

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

求圆的面积 （C语言代码）

打水问题 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-进制转换（C语言代码）

回文数字（C++代码）

　　评论区

求圆的面积（C语言代码）

打水问题（C语言代码）