难度: Medium
给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
示例 1：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,4,7,5,3,6,8,9]
示例 2：
输入：mat = [[1,2],[3,4]] 输出：[1,2,3,4]
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104-105 <= mat[i][j] <= 105运行时间: 54 ms
内存: 18.7 MB
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
m = len(mat)
n = len(mat[0])
ans = [[] for i in range(m+n-1)]
ans_flatten = []
for i in range(m):
for j in range(n):
ans[i+j].append(mat[i][j])
for i, li in enumerate(ans):
if i%2 == 0:
for j in range(len(li)-1, -1, -1):
ans_flatten.append(li[j])
else:
for j in range(len(li)):
ans_flatten.append(li[j])
return ans_flatten
这个题解采用了分组和遍历的策略来实现对角线遍历。首先，根据矩阵元素的坐标(i, j)，每个元素被分配到对应的对角线组里，这个组的索引是i+j。这意味着所有在同一个对角线上的元素会被放在同一个列表中。创建了一个列表数组ans来存储这些对角线组。然后，根据对角线的索引顺序，决定了遍历的方向：偶数索引的对角线从上到下遍历（逆序插入到结果列表中），奇数索引的对角线则从下到上遍历（顺序插入）。这样可以确保输出结果符合对角线遍历的要求。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
m = len(mat) # 获取矩阵的行数
n = len(mat[0]) # 获取矩阵的列数
ans = [[] for i in range(m+n-1)] # 创建足够的空列表以存储所有对角线的元素
ans_flatten = [] # 最终的结果列表
for i in range(m):
for j in range(n):
ans[i+j].append(mat[i][j]) # 将元素添加到对应的对角线列表中
for i, li in enumerate(ans): # 遍历每个对角线的列表
if i%2 == 0: # 偶数索引对角线逆序添加
for j in range(len(li)-1, -1, -1):
ans_flatten.append(li[j])
else: # 奇数索引对角线顺序添加
for j in range(len(li)):
ans_flatten.append(li[j])
return ans_flatten # 返回遍历结果
在一个矩阵中，每个元素的坐标是(i, j)，其中i是行索引，j是列索引。当我们考虑对角线遍历时，可以发现处于同一对角线上的元素满足i+j为常数。例如，从左上角到右下角第一条对角线上的元素坐标为(0,0)，第二条为(0,1), (1,0)，它们的i+j值分别是0和1。因此，使用i+j作为索引可以自然地将元素按其所在的对角线分组，便于后续的遍历处理。
这种处理方式基于对角线遍历的特定要求，即交替改变遍历元素的方向。从矩阵的左上角开始，首先向上遍历，然后改变方向向下遍历，再次改变方向向上遍历，依此类推。在实现中，使用偶数索引(i+j为偶数)的对角线逆序添加模拟了从下到上的遍历效果，而奇数索引的对角线则顺序添加，模拟从上到下的遍历效果。这样可以确保输出的顺序符合题目的对角线遍历要求。
是的，此添加方式考虑了元素在原矩阵中的顺序。由于是按照从左到右，从上到下的顺序遍历矩阵元素，因此在同一对角线(i+j值相同)上的元素会按照它们在原矩阵中出现的顺序被添加到对应的列表中。这确保了在同一对角线内的元素，其相对顺序是根据它们在矩阵中的位置决定的。
每个对角线列表分别处理逆序和顺序添加的方式是为了模拟对角线遍历中的方向变换。如果直接合并每个对角线的元素，无法实现所需的上下交替遍历的效果。通过逆序和顺序处理，可以确保对角线遍历的输出顺序符合题目要求，同时也避免了在遍历完成后再进行额外的排序或重排操作，提高了算法的效率。