对角线遍历

题目描述：

给你一个大小为 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 <= 104
1 <= m * n <= 104
-105 <= mat[i][j] <= 105

思路:

时间复杂度：O(n^2),空间复杂度O(n^2)

模拟法做，模拟对角线遍历

代码:

func findDiagonalOrder(mat [][]int) []int {
    m,n := len(mat),len(mat[0])
    k := 0
    var res,tmp []int
    for i := 0;i<n;i++{
        for j:=0;j<=i && j<m;j++{
            if i-j >=0 {
                tmp = append(tmp, mat[j][i-j])
            }
            
        }
        
        if k %2 == 0{
            tmp = reverse(tmp)
        }
        res = append(res,tmp...)
        k++
        tmp = []int{}
    }
    for i:=1;i<m;i++{
        for j:=0;j<=m-i-1  ;j++{
            if n-j-1 >=0{
                tmp = append(tmp, mat[i+j][n-j-1])
            }
            
        }
        if k %2 == 0{
            tmp = reverse(tmp)
        }
        k++
        res = append(res,tmp...)
        tmp = []int{}
    }
    return res
}

func reverse(a []int)[]int{
    for i:=0;i<len(a)/2;i++{
        a[i],a[len(a)-i-1] = a[len(a)-i-1], a[i]
    }
    return a
}

代码效率：

执行用时：80 ms, 在所有 Go 提交中击败了13.79%的用户
内存消耗：6.6 MB, 在所有 Go 提交中击败了90.18%的用户