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.length
  • n == mat[i].length
  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4
  • -10^5 <= mat[i][j] <= 10^5

解题思路

这道题要求按对角线顺序遍历矩阵。观察遍历规律可以发现：

  1. 对角线方向交替：奇数对角线向上遍历（右上方向），偶数对角线向下遍历（左下方向）
  2. 对角线识别：位置 (i,j) 所在对角线编号为 i+j
  3. 边界处理：当到达矩阵边界时需要调整起始位置

解法一：直接模拟 按照对角线方向移动，遇到边界时改变方向并调整位置。需要处理四种边界情况。

解法二：按对角线分组（推荐） 将所有元素按对角线编号 i+j 分组，然后根据对角线编号的奇偶性决定遍历顺序。偶数对角线正序遍历，奇数对角线逆序遍历。

第二种解法更清晰易懂，避免了复杂的边界判断，代码更简洁。

代码实现

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<int> result;
        map<int, vector<int>> diagonals;
        
        // 按对角线编号分组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                diagonals[i + j].push_back(mat[i][j]);
            }
        }
        
        // 按奇偶性决定遍历顺序
        for (auto& [diag, elements] : diagonals) {
            if (diag % 2 == 0) {
                // 偶数对角线：正序
                for (int val : elements) {
                    result.push_back(val);
                }
            } else {
                // 奇数对角线：逆序
                for (int i = elements.size() - 1; i >= 0; i--) {
                    result.push_back(elements[i]);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        diagonals = {}
        
        # 按对角线编号分组
        for i in range(m):
            for j in range(n):
                diag = i + j
                if diag not in diagonals:
                    diagonals[diag] = []
                diagonals[diag].append(mat[i][j])
        
        result = []
        # 按奇偶性决定遍历顺序
        for diag in sorted(diagonals.keys()):
            if diag % 2 == 0:
                # 偶数对角线：正序
                result.extend(diagonals[diag])
            else:
                # 奇数对角线：逆序
                result.extend(diagonals[diag][::-1])
        
        return result

public class Solution {
    public int[] FindDiagonalOrder(int[][] mat) {
        int m = mat.Length, n = mat[0].Length;
        var diagonals = new Dictionary<int, List<int>>();
        
        // 按对角线编号分组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int diag = i + j;
                if (!diagonals.ContainsKey(diag)) {
                    diagonals[diag] = new List<int>();
                }
                diagonals[diag].Add(mat[i][j]);
            }
        }
        
        var result = new List<int>();
        // 按奇偶性决定遍历顺序
        foreach (var kvp in diagonals.OrderBy(x => x.Key)) {
            if (kvp.Key % 2 == 0) {
                // 偶数对角线：正序
                result.AddRange(kvp.Value);
            } else {
                // 奇数对角线：逆序
                var reversed = new List<int>(kvp.Value);
                reversed.Reverse();
                result.AddRange(reversed);
            }
        }
        
        return result.ToArray();
    }
}

var findDiagonalOrder = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    const result = [];
    let row = 0, col = 0;
    let goingUp = true;
    
    for (let i = 0; i < m * n; i++) {
        result.push(mat[row][col]);
        
        if (goingUp) {
            if (col === n - 1) {
                row++;
                goingUp = false;
            } else if (row === 0) {
                col++;
                goingUp = false;
            } else {
                row--;
                col++;
            }
        } else {
            if (row === m - 1) {
                col++;
                goingUp = true;
            } else if (col === 0) {
                row++;
                goingUp = true;
            } else {
                row++;
                col--;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历矩阵中的每个元素一次
空间复杂度O(m × n)需要额外存储空间来分组对角线元素

相关题目