给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

示例:

输入:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

输出: [1,2,4,7,5,3,6,8,9]

解释:

说明:

1. 给定矩阵中的元素总数不会超过 100000 。

Solution

参考 @jimmy00745 的解题思路

• 对角线特征
  • 对角线的总数为 = 行数 + 列数 - 1
  • 对角线向右上或者向左下是交替进行的，当对角线的序号为偶数时，对角线是向右上的。
• 数据行列特征
  • 在一条对角线上，行和列的序号加起来是恒定的，因为如果行 +1 了则列必定 -1。
  • 确定行（或列）的起始与结束范围。
• 行的起始
  • 在对角线小于等于列数的时候，观察到始终是从第 ０ 行开始。
  • 超过了列数后，每超过一条，起始行数也要加一。即 curve_line + 1 - Ｎ。
• 行的结束
  • 从最后一行看，当对角线数大于等于行数时，观察到始终到第M行结束，即索引为 M-1。
  • 当对角线小于行数时，观察到每少一条，结束行数也 -1。即 curve_line。

# @lc code=start
class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []
        m, n, res = len(matrix), len(matrix[0]), []
        for curve in range(m+n-1):
            row_begin = 0 if curve+1 <= n else curve+1-n
            row_end = m-1 if curve+1 >= m else curve
            if curve % 2 == 1:
                for i in range(row_begin, row_end+1):
                    res.append(matrix[i][curve-i])
            else:
                for i in range(row_end, row_begin-1, -1):
                    res.append(matrix[i][curve-i])
        return res
# @lc code=end