uq_43625241302

用户名：uq_43625241302

访问量：3158

签　名：

等　　级
排　　名	7726
经　　验	1287
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

预处理 + 双端队列
浏览：364

你可能喜欢

预处理 + 双端队列

　　作者: uq_43625241302　　　　发表时间：2023-06-09 14:36:02 浏览：364　|　评论：1　

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

# 预处理 + 单调队列 + 滑动窗口
## 前言
俗话说的好，先易后难。我们先看一下这道题的一维版本：[1438. 绝对差不超过限制的最长连续子数组
](https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/)
即在一维数组中找到一个最大值减最小值小于limit的最长的子数组。
对于这种问题，我们可以思考维护一个滑动的窗口，同时能快速获取到这个窗口内的最大最小值，同时删除最值后能获取到下一个最值。
> 如何快速获取窗口内的最大最小值呢？

可以考虑维护两个单调队列，一个用来存储最小值，一个用来存储最大值。当最小值的队列应该是单调递增的，最大值的队列应该是单调递减的。以最小值队列为例，因为当后续出现的值比当前值更小时，因为窗口是向右滑动的，当前值就必然不可能是最小值，因此可以出队。
举个例子，数组为[10,1,2,4,7,2]，limit = 5，首先`maxQueue = [10]`，`minQueue = [10]`。此时移动窗口右指针进行遍历
* 遍历到`1`，则将`minQueue`中的`10`出队，因为`10`不再具有成为最小值的可能，此时`maxQueue = [10， 1]`，`minQueue = [1]`
	* 此时`max - min > limit`，将左指针右移，同时删除队列中的元素，此时`maxQueue = [1]`，`minQueue = [1]`
* 遍历到`2`，则将`maxQueue`中的`1`出队，因为`1`不再具有成为最大值的可能，`maxQueue = [2]`，`minQueue = [1， 2]`
	* 此时`max - min <= limit`，更新答案`res = Math.max(res, r - l + 1)`
* 重复上述步骤

## 一维代码实现
```java
public int longestSubarray(int[] nums, int limit) {
        int n = nums.length, l = 0, res = 1;
        Deque<Integer> minQueue = new LinkedList<>();	// 记录窗口最小值
        Deque<Integer> maxQueue = new LinkedList<>();	// 记录窗口最大值
        for(int i = 0; i < n; i++) {
			// 保证最小值队列递增
            while(!minQueue.isEmpty() && minQueue.peekLast() > nums[i]) minQueue.pollLast();
            minQueue.addLast(nums[i]);
			// 保证最大值队列递减
            while(!maxQueue.isEmpty() && maxQueue.peekLast() < nums[i]) maxQueue.pollLast();
            maxQueue.addLast(nums[i]);
			// 差值大于limit，左指针右移
            if(maxQueue.peek() - minQueue.peek() > limit) {
                while(!minQueue.isEmpty() && !maxQueue.isEmpty() && maxQueue.peek() - minQueue.peek() > limit) {
                    if(nums[l] == minQueue.peek()) minQueue.pollFirst();
                    if(nums[l++] == maxQueue.peek()) maxQueue.pollFirst();
                }
            }
            res = Math.max(res, i - l + 1);
        }
        return res;
    }
```

## 解题思路
进行了一维的训练，接下来目的就是将二维转换为一维。
二维的暴力思路是枚举左上角`(x1, y1)`和右下角`(x2, y2)`，然后遍历整个子矩阵。但这样时间复杂度过高，为$$O(m^2n^2) \times 计算子矩阵是否符合要求所需要的时间复杂度$$，这是过不了的。
> 将二维转换为一维

可以先枚举`x1`和`x2`，然后计算每一列从`x1`到`x2`的最大最小值。此时就转换为了一个一维的问题。

> 如何计算每一列从`x1`到`x2`的最大最小值

可以进行预处理，用一个三维数组`max[i][j][k]` 表示第`i`列在区间`[j, k]`的最大值。用另一个三维数组`min[i][j][k]` 表示第`i`列在区间`[j, k]`的最小值。预处理数组的时间复杂度为$$O(mn^2)$$，因为$$m \times n <= 10^5$$且$$ n <= 80$$，所以是符合复杂度要求的。空间复杂度为$$O(mn^2)$$

## 代码实现
```java
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 一维题目：双端队列 O(n)时间复杂度
 * https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/
 */
public class Main {
    public static void main(String[] args) {
        new Main().go();
    }

// max[i][j][k] 表示第 i列，区间为[j, k] 的最大值
    private int[][][] max;
    // min[i][j][k] 表示第 i列，区间为[j, k] 的最小值
    private int[][][] min;
    private int[][] matrix;
    private int limit;
    public void go() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        max = new int[m][n][n];
        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.println(res);
    }

public int getRes() {
        int n = matrix.length, m = matrix[0].length, res = 1;
        // 遍历上下边界 x1 x2
        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, 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);
        }
        return res;
    }
}
```

## 复杂度分析
总的时间复杂度为 $$O(mn^2)$$，空间复杂度为 $$O(mn^2)$$

0.0分

8 人评分

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

　　评论区

SQY666

什么水平才能在比赛中做出来这种题

2024-03-25 13:57:48

uq_43625241302

TA的其他文章

你可能喜欢

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

C二级辅导-统计字符（C语言代码）

单词个数统计（C++代码）

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

点我有惊喜！你懂得！

预处理 + 双端队列

评论区

精彩推荐

C语言训练-最大数问题（C语言代码）.........关于-1

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

C二级辅导-等差数列（C语言代码）

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

字符串问题（C语言代码）

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

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

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

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

uq_43625241302

TA的其他文章

你可能喜欢

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

C二级辅导-统计字符 （C语言代码）

单词个数统计 （C++代码）

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

点我有惊喜！你懂得！

预处理 + 双端队列

评论区

精彩推荐

C语言训练-最大数问题 （C语言代码）.........关于-1

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

C二级辅导-等差数列 （C语言代码）

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

字符串问题 （C语言代码）

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

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

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

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

C二级辅导-统计字符（C语言代码）

单词个数统计（C++代码）

　　评论区

C语言训练-最大数问题（C语言代码）.........关于-1

C二级辅导-等差数列（C语言代码）

字符串问题（C语言代码）