Diagonal Traverse

题目介绍

LeetCode 498. Diagonal Traverse。

复杂度

时间复杂度: O(mn), 空间复杂度: O(mn)

解题思路

边界条件很多，用 (i+j)%2 判断是 ↗ 还是 ↙ ，不同情况中还要判断转向的条件。

class Solution {
    func findDiagonalOrder(_ matrix: [[Int]]) -> [Int] {
        var i = 0
        var j = 0
        var ans: [Int] = []
        while (i < matrix.count && j < matrix[0].count) {
            ans.append(matrix[i][j])
            if (i + j) % 2 == 0 {
                // ↗ 
                if j == matrix[0].count - 1 {
                    // 右边到顶了，要换方向，坐标(i+1, j)
                    i += 1
                } else if i == 0 {
                    // 上面到顶了，要换方向，坐标(i, j+1)
                    j += 1
                } else {
                    // 不换方向，坐标(i-1, j+1)
                    i -= 1
                    j += 1
                }
            } else {
                // ↙ 
                if i == matrix.count - 1 {
                    // 下边到底了，要换方向，坐标(i, j+1)
                    j += 1
                } else if j == 0 {
                    // 左边到底了，要换方向，坐标(i+1, j)
                    i += 1
                } else {
                    // 不换方向
                    i += 1
                    j -= 1
                }
            }
        }
        return ans
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/03/05/DiagonalTraverse/