498. 对角线遍历

题目描述

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

输入输出

1
2
输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

基本思路

模拟打印出来的全过程 一共有m + n - 1条对角线 如果是偶数 则从下往上 奇数 则从上往下

  • 当第 i 条对角线从下往上遍历时，每次行索引减 1，列索引加 1，直到矩阵的边缘为止：

    • 当 i < m 时，则此时对角线遍历的起点位置为 (i,0)；

    • 当 i ≥ m 时，则此时对角线遍历的起点位置为 (m - 1, i - m + 1)；

  • 当第 i 条对角线从上往下遍历时，每次行索引加 1，列索引减 1，直到矩阵的边缘为止：

    • 当 i < n 时，则此时对角线遍历的起点位置为 (0, i)；
    • 当 i ≥ n 时，则此时对角线遍历的起点位置为 (i - n + 1, n - 1)；

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] res = new int[m * n];
        int pos = 0;
        for(int i = 0; i < m+n-1; i++) {
            if(i % 2 == 1){
                int x = i < n ? 0 : i - n + 1;
                int y = i < n ? i : n - 1;
                while(x < m && y >= 0){
                    res[pos] = mat[x][y];
                    pos++;
                    x++;y--;
                }
            }else{
                int x = i < m ? i : m - 1;
                int y = i < m ? 0 : i - m + 1;
                while(x >= 0 && y < n){
                    res[pos] = mat[x][y];
                    pos++;
                    x--;y++;
                } 
            }
        }
        return res;
    }
}