题目描述

给你一个列表 nums ，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。

样例

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

输入：nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
输出：[1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

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

输入：nums = [[1,2,3,4,5,6]]
输出：[1,2,3,4,5,6]

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i].length <= 10^5
• 1 <= nums[i][j] <= 10^9
• nums 中最多有 10^5 个数字。

算法分析

枚举

若用二维数组直接构建出来，再斜对角线枚举，会爆空间和时间，因此需要找规律

• 1、可以观察到每个元素的坐标(i,j)中，i + j值是表示该点所对应的对角线
• 2、枚举每一行的元素，放在对应的链表中，例如当前坐标是(i,j)，因此它需要放在list[i + j]的链表中
• 3、从0到n + m - 1,枚举每个对角线链表，输出每个元素，又因为在当前链表中，先放的会在后面才用到，因此对于每个链表，需要从链表尾枚举到头输出

时间复杂度 $O(10^5)$

最多有10^5个元素

Java 代码

class Solution {
    static int N = 100010;
    ArrayList[] list = new ArrayList[N * 2];
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        int n = nums.size();
        int m = 0;
        for(int i = 0;i < nums.size();i ++) m = Math.max(m, nums.get(i).size());

        for(int i = 0;i < n + m;i ++) list[i] = new ArrayList<Integer>();

        int cnt = 0;//记录有多少个元素
        for(int i = 0;i < n;i ++)
        {
            List<Integer> t = nums.get(i);
            for(int j = 0;j < t.size();j ++)
            {
                list[i + j].add(t.get(j));
                cnt ++;
            }
        }
        //枚举对角线链表
        int[] ans = new int[cnt];
        int k = 0;
        for(int i = 0;i < n + m;i ++)
        {
            List<Integer> t = list[i];
            for(int j = t.size() - 1;j >= 0;j --) ans[k ++] = t.get(j);
        }
        return ans;
    }
}