zhongjl

用户名：dotcpp0649373

访问量：482

签　名：

等　　级
排　　名	18334
经　　验	748
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	江西财经大学
专　　业

　　自我简介：

TA的其他文章

找规律,凑组合
浏览：63

你可能喜欢

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

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

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

预处理+二分+单调队列求区间最值

　　作者: zhongjl　　　　发表时间：2023-04-05 03:33:06 浏览：150　|　评论：0　

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

本体思路
1.预处理矩阵O(N^2 M)
2.枚举行O(N^2),二分矩阵的宽度(log(M))
3.单调队列求区间最大最小值 O(M)
总的时间复杂度为  O(N N M log M)
空间复杂度为O(N N M)
```java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer sc = new StreamTokenizer(br);
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

public static int nextInt() throws IOException {
        sc.nextToken();
        return (int) sc.nval;
    }

public static int M, N, arr[][], limit;
    //使用单调队列,具体可以看
    public static boolean check(int x1, int x2, int k) {
        Deque<Integer> minq = new ArrayDeque<>();
        Deque<Integer> maxq = new ArrayDeque<>();
        for (int i = 0; i < M; i++) {
            if (i >= k && !minq.isEmpty() && minq.getFirst() == min[i - k][x1][x2]) {
                minq.removeFirst();
            }
            if (i >= k && !maxq.isEmpty() && maxq.getFirst() == max[i - k][x1][x2]) {
                maxq.removeFirst();
            }
            while (!minq.isEmpty() && min[i][x1][x2] < minq.getLast()) {
                minq.removeLast();
            }
            while (!maxq.isEmpty() && max[i][x1][x2] > maxq.getLast()) {
                maxq.removeLast();
            }
            minq.add(min[i][x1][x2]);
            maxq.add(max[i][x1][x2]);
            if (i - 0 + 1 >= k) {
                int minmin = minq.getFirst();
                int maxmax = maxq.getFirst();
                if (maxmax - minmin <= limit) {
                    return true;
                }
            }
        }
        return false;
    }

public static int min[][][];
    public static int max[][][];

public static void main(String[] args) throws IOException {
        N = nextInt();
        M = nextInt();
        arr = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                arr[i][j] = nextInt();
            }
        }
        limit = nextInt();
        min = new int[M][N][N];
        max = new int[M][N][N];
        // 枚举行(n*n),判断每一列的左端点,使用二分的方法判断右端点
        // 思路,预处理每一列的最大最小值,放在每一列的最后,这样在判断矩阵的稳定度的时候只需要判断该列即可
        // 对预处理后的每一列的最值,进行每一行的最值的预处理
        // col,row1,row2 M,N,N col表示每一列.row1表示列的上界,row2表示列的下界
        for (int col = 0; col < M; col++) {
            for (int row1 = 0; row1 < N; row1++) {
                for (int row2 = row1; row2 < N; row2++) {
                    if (row1 == row2) {
                        min[col][row1][row2] = arr[row1][col];
                        max[col][row1][row2] = arr[row1][col];
                        continue;
                    }
                    min[col][row1][row2] = Math.min(min[col][row1][row2 - 1], arr[row2][col]);
                    max[col][row1][row2] = Math.max(max[col][row1][row2 - 1], arr[row2][col]);

}
            }
        }
        int s = Integer.MIN_VALUE;
        for (int row1 = 0; row1 < N; row1++) {
            for (int row2 = row1; row2 < N; row2++) {
                int left = 1, right = M;
                if (check(row1, row2, right - left + 1)) { // 避免下面的mid+1越界
                    s = Math.max(s, (row2 - row1 + 1) * (right - left + 1));
                    continue;
                }
                while (left <= right) {
                    int mid = (left + right) / 2;
                    boolean t = check(row1, row2, mid);
                    if (t == true && check(row1, row2, mid + 1) == false) {
                        s = Math.max(s, (row2 - row1 + 1) * (mid));
                        break;
                    }
                    if (t == true) { // mid是true,mid+1也是true
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
        }
        System.out.println(s);
    }
}

```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zhongjl

TA的其他文章

你可能喜欢

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

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

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

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

C二级辅导-同因查找（C语言代码）

预处理+二分+单调队列求区间最值

评论区

精彩推荐

简单的a+b （C语言代码）

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

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

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

三角形（C++代码）记忆化搜索

母牛的故事（C语言代码）

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

图形输出（C语言代码）

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

判定字符位置（C++代码）

zhongjl

TA的其他文章

你可能喜欢

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

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

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

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

C二级辅导-同因查找 （C语言代码）

预处理+二分+单调队列求区间最值

评论区

精彩推荐

简单的a+b （C语言代码）

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

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

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

三角形 （C++代码）记忆化搜索

母牛的故事 （C语言代码）

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

图形输出 （C语言代码）

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

判定字符位置 （C++代码）

C二级辅导-同因查找（C语言代码）

　　评论区

三角形（C++代码）记忆化搜索

母牛的故事（C语言代码）

图形输出（C语言代码）

判定字符位置（C++代码）