Задача: 1424. Diagonal Traverse II
Сложность: medium

Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке.

Пример:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

👨‍💻 Алгоритм:

1⃣Инициализируйте очередь с (0, 0) и список ответов ans.

2⃣Пока очередь не пуста:
Извлеките (row, col) из очереди.
Добавьте nums[row][col] в ans.
Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь.
Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь.

3⃣Верните ans.

😎 Решение:

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        queue<pair<int, int>> q;
        q.push({0, 0});
        vector<int> ans;
        
        while (!q.empty()) {
            auto [row, col] = q.front(); q.pop();
            ans.push_back(nums[row][col]);
            
            if (col == 0 && row + 1 < nums.size()) {
                q.push({row + 1, col});
            }
            
            if (col + 1 < nums[row].size()) {
                q.push({row, col + 1});
            }
        }
        
        return ans;
    }
};

Ставь 👍 и забирай 📚 Базу знаний