【循环5】最大值查询问题③

前言

• 二维矩阵

二维矩阵:

Python中的二维矩阵可以理解为一个矩阵或表格，它由行和列组成。二维矩阵可以用列表（List）来表示，在Python中，二维列表是一种存储数据的结构，它具有两个索引：一个表示行，另一个表示列。

定义二维矩阵

在Python中，可以通过以下方式定义一个二维列表（矩阵）：

# 定义一个3行4列的整数二维矩阵
matrix = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]
]

这意味着 matrix 是一个包含3行4列的整数矩阵，每个元素都可以通过两个索引来访问，第一个索引表示行，第二个索引表示列。

初始化二维矩阵

1. 静态初始化：你可以在声明时直接初始化二维矩阵的元素。例如：

   # 一个2行3列的二维矩阵
   matrix = [
       [1, 2, 3],
       [4, 5, 6]
   ]
   

2. 逐个赋值：你可以通过循环或直接给元素赋值来初始化矩阵。

   # 定义一个2行3列的矩阵
   matrix = [
       [0, 0, 0],
       [0, 0, 0]
   ]
   
   matrix[0][0] = 1
   matrix[0][1] = 2
   matrix[0][2] = 3
   matrix[1][0] = 4
   matrix[1][1] = 5
   matrix[1][2] = 6
   
   print(matrix)
   

   输出：

   [[1, 2, 3], [4, 5, 6]]
   

访问二维矩阵的元素

通过指定行号和列号，你可以访问或修改矩阵中的任何元素。例如：

matrix = [
    [1, 2, 3],
    [4, 5, 6]
]

value = matrix[1][2]  # 访问第二行第三列的元素，值为6
print(value)  # 输出: 6

matrix[0][1] = 10  # 将第一行第二列的元素修改为10
print(matrix[0][1])  # 输出: 10

输出：

6
10

使用循环遍历二维矩阵

你可以使用两个嵌套的循环来遍历二维矩阵中的所有元素：

matrix = [
    [1, 2, 3],
    [4, 5, 6]
]

for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        print(matrix[i][j], end=' ')  # 输出每个元素
    print()  # 换行

输出：

1 2 3 
4 5 6 

动态分配二维矩阵

如果你不知道矩阵的大小，可以使用动态方法来创建二维矩阵。例如，使用列表推导式来分配内存：

rows, cols = 2, 3
matrix = [[0 for _ in range(cols)] for _ in range(rows)]  # 为每行分配列数

# 初始化矩阵
matrix[0][0] = 1
matrix[0][1] = 2
matrix[0][2] = 3
matrix[1][0] = 4
matrix[1][1] = 5
matrix[1][2] = 6

print(matrix)

输出：

[[1, 2, 3], [4, 5, 6]]

使用 vector 创建二维数组（Python中的列表嵌套）

在Python中，嵌套列表（List of Lists）可以实现与C++中vector<vector<int>>类似的二维数组结构。

# 创建一个3行4列的二维列表
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]

# 输出矩阵的所有元素
for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        print(matrix[i][j], end=' ')
    print()

输出：

1 2 3 4 
5 6 7 8 
9 10 11 12 

解释

1. 定义二维列表：matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] 这行代码创建了一个 3 行 4 列的二维矩阵。外层列表包含了 3 个子列表，每个子列表表示一行，并初始化为4列。

2. 初始化矩阵元素：通过 matrix[i][j] 语法访问和设置每个元素的值。

3. 遍历输出矩阵：使用嵌套的 for 循环遍历二维矩阵，打印出每个元素。

动态调整大小

与传统的数组不同，Python的列表可以在运行时动态调整大小。例如，可以使用 append 方法增加行或列：

# 增加一行
new_row = [13, 14, 15, 16]
matrix.append(new_row)

# 增加一列
for row in matrix:
    row.append(0)

print(matrix)

输出：

[[1, 2, 3, 4, 0], [5, 6, 7, 8, 0], [9, 10, 11, 12, 0], [13, 14, 15, 16, 0]]

总结

Python中的二维列表是一种非常常见的数据结构，通常用来存储和处理表格或网格类型的数据。你可以通过嵌套列表、列表推导式以及动态方法来实现二维列表的存储，且访问元素时需要使用两个索引（行和列）。通过循环遍历，你可以对矩阵中的元素进行处理。

题解

题面分析

这道题本质和之前的两题一样是查询最大值的问题，不同的是之前两题都是一维数组，而这题是二维数组。

具体来说，给定一个二维整数矩阵和多个查询，每个查询指定一个子矩阵的左上角和右下角坐标。对于每个查询，我们需要在指定的子矩阵范围内找到最大值并输出该最大值。

思路

思路其实和上一题一样也是三重循环枚举，不同的是这题是要读入一个二维矩阵，所以我们先给大家补充了二维矩阵的使用方式。如下:

matrix = [[0 for _ in range(m)] for _ in range(n)]

# 输入矩阵元素
for i in range(n):
    for j in range(m):
        matrix[i][j] = int(input())

学会了二维，三维四维也就很简单了，基本原理都是一样的。本题代码如下:

解释

1. 输入读取：

   • 使用 sys.stdin.read() 一次性读取所有输入，并通过 split() 分割成列表 data，以提高读取效率。
   • n 和 m 分别为矩阵的行数和列数。
   • 通过循环读取矩阵的每个元素并存储到 matrix 列表中。

2. 查询处理：

   • 读取查询次数 q。
   • 对于每个查询，读取四个整数 x1, y1, x2, y2，分别表示子矩阵的左上角和右下角坐标。
   • 将坐标从1开始转换为0开始，以便于Python列表的索引操作。
   • 初始化 max_val 为子矩阵的第一个元素 matrix[x1][y1]。
   • 使用嵌套的 for 循环遍历子矩阵范围，更新 max_val 为当前遇到的最大值。

3. 结果输出：

   • 对于每个查询，打印找到的最大值 max_val。

示例

输入

3 4
1 2 3 4
5 6 7 8
9 10 11 12
2
1 1 2 3
2 2 3 4

输出

7
12

解释

• 第一个查询 [1,1] 到 [2,3]：

  1 2 3
  5 6 7
  

  最大值为 7。
• 第二个查询 [2,2] 到 [3,4]：

  6 7 8
  10 11 12
  

  最大值为 12。

注意事项

• 下标转换：题目通常使用1-based索引，而Python列表使用0-based索引。因此，在处理时需要将输入的坐标减1。
• 输入处理：使用 sys.stdin.read() 可以提高读取效率，特别是当数据量较大时。
• 效率：此方法适用于数据规模较小的情况。如果数据规模较大，可以考虑预处理如稀疏表（Sparse Table）或其他优化方法来提升查询效率。

完整代码示例

def main():
    # 输入矩阵的行和列
    n, m = map(int, input().split())
    
    # 创建并输入矩阵
    matrix = []
    for i in range(n):
        row = list(map(int, input().split()))
        matrix.append(row)
    
    # 输入查询次数
    q = int(input())
    
    while q > 0:
        q -= 1
        # 输入查询的坐标
        x1, y1, x2, y2 = map(int, input().split())
        
        # 转换为 0-indexed
        x1 -= 1
        y1 -= 1
        x2 -= 1
        y2 -= 1
        
        # 初始化最大值
        max_val = matrix[x1][y1]
        
        # 遍历子矩阵寻找最大值
        for i in range(x1, x2 + 1):
            for j in range(y1, y2 + 1):
                max_val = max(max_val, matrix[i][j])
        
        # 输出结果
        print(max_val)

if __name__ == "__main__":
    main()

题目描述：

给定一个整数矩阵 $matrix$，您需要处理多个查询。每个查询包含一个子矩阵的左上角和右下角的坐标 $[(x_1, y_1), (x_2, y_2)]$，请您找出该子矩阵内的最大值。

输入：

• 第一行输入两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 100)$，分别表示矩阵的行数和列数。
• 接下来 $n$ 行，每行输入 $m$ 个整数 $matrix[i][j]$ $(1 \leq matrix[i][j] \leq 10^6)$，表示矩阵的元素。
• 第 $n+2$ 行输入一个整数 $q$ $(1 \leq q \leq 100)$，表示查询的次数。
• 接下来 $q$ 行，每行输入四个整数 $x_1, y_1, x_2, y_2$$1<=x_1<=x_2<=n, 1<=y_1<=y_2<=m$，表示查询的子矩阵的左上角和右下角的坐标（注意：下标从 1 开始计数）。

输出：

对于每个查询，输出一个整数，表示该子矩阵内的最大值。

示例：

输入：

3 3
1 2 3
4 5 6
7 8 9
2
1 1 2 2
1 2 3 3

输出：

5
9

提示：

• 查询的子矩阵包括左上角和右下角的元素。
• 由于矩阵下标从 1 开始，注意转换下标。