498. Diagonal Traverse

public class Solution {
    public int[] FindDiagonalOrder(int[][] mat) {
        if (mat == null || mat.Length == 0) return new int[0];
        int N = mat.Length, M = mat[0].Length;
        List<int> result = new List<int>();
        
        for (int d = 0; d < N + M - 1; ++d) {
            List<int> intermediate = new List<int>();
            int r = d < M ? 0 : d - M + 1;
            int c = d < M ? d : M - 1;
            
            while (r < N && c >= 0) {
                intermediate.Add(mat[r][c]);
                r++;
                c--;
            }
            
            if (d % 2 == 0) {
                intermediate.Reverse();
            }
            result.AddRange(intermediate);
        }
        
        return result.ToArray();
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& FindDiagonalOrder(int[][] mat) {
        if (mat == null || mat.size() == 0) return new int[0];
        int N = mat.size(), M = mat[0].size();
        List<int> result = new List<int>();
        
        for (int d = 0; d < N + M - 1; ++d) {
            List<int> intermediate = new List<int>();
            int r = d < M ? 0 : d - M + 1;
            int c = d < M ? d : M - 1;
            
            while (r < N && c >= 0) {
                intermediate.push_back(mat[r][c]);
                r++;
                c--;
            }
            
            if (d % 2 == 0) {
                intermediate.Reverse();
            }
            result.AddRange(intermediate);
        }
        
        return result.ToArray();
    }
}

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }
        
        int N = matrix.length;
        int M = matrix[0].length;
        
        int[] result = new int[N*M];
        int k = 0;
        ArrayList<Integer> intermediate = new ArrayList<Integer>();
        
        for (int d = 0; d < N + M - 1; d++) {
            
            intermediate.clear();
            
            int r = d < M ? 0 : d - M + 1;
            int c = d < M ? d : M - 1;
            
            while (r < N && c > -1) {
                
                intermediate.add(matrix[r][c]);
                ++r;
                --c;
            }
                
            if (d % 2 == 0) {
                Collections.reverse(intermediate);
            }
            
            for (int i = 0; i < intermediate.size(); i++) {
                result[k++] = intermediate.get(i);
            }
        }
        return result;
    }
}

class Solution {
    findDiagonalOrder(mat) {
        if (!mat.length || !mat[0].length) return [];
        const N = mat.length, M = mat[0].length;
        const result = [];
        
        for (let d = 0; d < N + M - 1; ++d) {
            const intermediate = [];
            let r = d < M ? 0 : d - M + 1;
            let c = d < M ? d : M - 1;
            
            while (r < N && c >= 0) {
                intermediate.push(mat[r][c]);
                r++;
                c--;
            }
            
            if (d % 2 === 0) {
                intermediate.reverse();
            }
            result.push(...intermediate);
        }
        
        return result;
    }
}

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        if not mat or not mat[0]:
            return []
        
        N, M = len(mat), len(mat[0])
        result = []
        
        for d in range(N + M - 1):
            intermediate = []
            r = 0 if d < M else d - M + 1
            c = d if d < M else M - 1
            
            while r < N and c > -1:
                intermediate.append(mat[r][c])
                r += 1
                c -= 1
            
            if d % 2 == 0:
                result.extend(intermediate[::-1])
            else:
                result.extend(intermediate)
        
        return result

func findDiagonalOrder(mat [][]int) []int {
    if len(mat) == 0 || len(mat[0]) == 0 {
        return []int{}
    }
    N, M := len(mat), len(mat[0])
    result := []int{}
    
    for d := 0; d < N + M - 1; d++ {
        intermediate := []int{}
        r := 0
        if d >= M {
            r = d - M + 1
        }
        c := d
        if d >= M {
            c = M - 1
        }
        
        for r < N && c >= 0 {
            intermediate = append(intermediate, mat[r][c])
            r++
            c--
        }
        
        if d % 2 == 0 {
            for i := len(intermediate) - 1; i >= 0; i-- {
                result = append(result, intermediate[i])
            }
        } else {
            result = append(result, intermediate...)
        }
    }
    
    return result
}

Algorithm

Инициализация и подготовка

Проверьте, пуста ли матрица. Инициализируйте переменные для хранения размеров матрицы. Создайте массив result для хранения окончательных результатов и временный список intermediate для промежуточных значений диагоналей.

Итерация по диагоналям

Внешний цикл для прохождения по всем диагоналям. Головы диагоналей находятся в первой строке и последнем столбце. Внутренний цикл для итерации по элементам каждой диагонали. Индексы элементов диагонали изменяются до выхода за пределы матрицы.

Обработка диагоналей

Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result.

😎