难度: Medium
给你一个列表 nums ，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。
示例 1：
输入：nums = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,4,2,7,5,3,8,6,9]
示例 2：
输入：nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] 输出：[1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
示例 3：
输入：nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]] 输出：[1,4,2,5,3,8,6,9,7,10,11]
示例 4：
输入：nums = [[1,2,3,4,5,6]] 输出：[1,2,3,4,5,6]
提示：
1 <= nums.length <= 10^51 <= nums[i].length <= 10^51 <= nums[i][j] <= 10^9nums 中最多有 10^5 个数字。运行时间: 107 ms
内存: 29.9 MB
class Solution:
def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
""" use of queue. time compelxity O(M*N) """
queue = collections.deque([(0, 0)])
ans = []
while queue:
row, col = queue.popleft()
ans.append(nums[row][col])
# check the validity of new row
if col == 0:
if row+1 < len(nums):
col_len = len(nums[row+1])
if col < col_len:
queue.append((row+1, col))
# check the validity of new col
if col+1 < len(nums[row]):
queue.append((row, col+1))
return ans
该题解使用了广度优先搜索（BFS）的方法来遍历二维列表。具体来说，利用一个队列来存储下一个要访问的元素的坐标（行和列）。初始时，队列中只有元素 (0,0)，即第一个元素。在每次循环中，从队列中取出一个元素坐标，将对应的值加入到结果列表中。接着，如果该元素是其行的第一个元素且下一行存在，尝试将下一行的同列元素加入队列。此外，如果该元素的下一列在当前行中存在，则将该列的元素加入队列。这样的处理保证了遍历的顺序符合题目要求的对角线顺序。
时间复杂度: O(N)
空间复杂度: O(N)
# Definition of the Solution class with a method to find diagonal order traversal of 'nums'
class Solution:
def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
# Initialize the queue with the first element's position
queue = collections.deque([(0, 0)])
ans = [] # This will store the result
while queue:
row, col = queue.popleft() # Get the next element's position
ans.append(nums[row][col]) # Append the element to the result list
# Check if the next row should be considered
if col == 0 and row + 1 < len(nums):
if col < len(nums[row + 1]):
queue.append((row + 1, col)) # Add next row, same column element
# Check if the next column in the same row should be considered
if col + 1 < len(nums[row]):
queue.append((row, col + 1)) # Add same row, next column element
return ans # Return the collected elements
算法通过控制元素入队的顺序来确保按对角线顺序处理。首先，队列初始化时仅包含(0, 0)。对于每个元素，如果它是其行的第一个元素且下一行存在，则将下一行的第一个元素加入队列（保持对角线的纵向顺序）。同时，如果当前元素的右侧元素存在（即同行的下一列元素），则将其加入队列。这种左到右，上到下的顺序添加确保了元素是按照对角线方向遍历的。
算法在尝试访问或加入队列中的元素之前，总是检查当前行和列的索引是否有效。对于每个元素，算法检查下一列是否存在于当前行（`col + 1 < len(nums[row])`），以及是否存在下一行的同列元素（`col < len(nums[row + 1])`），这样的检查确保了不会访问不存在的索引，从而避免索引越界错误。
这种设计是为了避免重复加入同一元素多次到队列中。如果每个元素处理时都考虑下一行的同列元素，则每行的首个元素将被重复加入多次，导致不必要的重复处理和性能下降。因此，只有当处理到当前行的第一个元素时，才将下一行的首个元素加入队列，这样可以保证每个元素只被处理一次。
是的，每次从队列中取出一个元素时，算法需要检查该元素的下一列是否存在于当前行中。这是通过比较当前列的索引加一（`col + 1`）与当前行的长度（`len(nums[row])`）来实现的。这种检查是必要的，以确保不会尝试访问当前行不存在的列，从而避免索引越界错误。