对角线遍历
给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例
输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]
思路
解法1：
这道题的关键是「找规律」和「考虑边界问题」。
找规律：
当行号 + 列号为偶数时，遍历方向为从左下到右上。可以记为右上方向（-1, +1），即行号 -1，列号 +1。 当行号 + 列号为奇数时，遍历方向为从右上到左下。可以记为左下方向（+1, -1），即行号 +1，列号 -1。 边界情况：
- 向右上方向移动时：
- 如果在最后一列，则向下方移动，即 x += 1。
- 如果在第一行，则向右方移动，即 y += 1。
- 其余情况想右上方向移动，即 x -= 1、y += 1。
- 向左下方向移动时：
- 如果在最后一行，则向右方移动，即 y += 1。
- 如果在第一列，则向下方移动，即 x += 1。
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
rows = len(mat)
cols = len(mat[0])
count = rows * cols
x, y = 0, 0
ans = []
for i in range(count):
ans.append(mat[x][y])
if (x + y) % 2 == 0:
# 最后一列
if y == cols - 1:
x += 1
# 第一行
elif x == 0:
y += 1
# 右上方向
else:
x -= 1
y += 1
else:
# 最后一行
if x == rows - 1:
y += 1
# 第一列
elif y == 0:
x += 1
# 左下方向
else:
x += 1
y -= 1
return ans
解法2：
有两种遍历方向，每次循环把一个方向的数据放到数组中，到达边界，改变方向.
遍历次数为m + n - 1,确定方向对2进行取余
边界处理：
- 右上方向
- k < n: j++
- k >=n: j+2, k-1
- 左下方向
- j < m: k++
- j >=m: k+2, j-1
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
if not mat or not mat[0]:
return []
m, n = len(mat), len(mat[0])
j, k = 0, 0
count = m + n - 1
index = 0
res = [0] * (m * n)
for i in range(count):
if i % 2 == 0: # 右上方向
while j >= 0 and k < n:
res[index] = mat[j][k]
index += 1
j -= 1
k += 1
if k < n:
j += 1
else:
j += 2
k -= 1
else: # 左下方向
while j < m and k >= 0:
res[index] = mat[j][k]
index += 1
j += 1
k -= 1
if j < m:
k += 1
else:
j -= 1
k += 2
return res