LeetCode 1424. Diagonal Traverse II

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,4,2,7,5,3,8,6,9]

Example 2:

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]

Constraints:

• 1 <= nums.length <= 105

• 1 <= nums[i].length <= 105

• 1 <= sum(nums[i].length) <= 105

• 1 <= nums[i][j] <= 105

在一个对角线是有一个规律的，就是同一个对角线上面的index相加是一样的，因为i++的时候，j--了，所以i+j是一样的，

考虑到这一点，我们就把i+j 放到map中的key中，然后相同的i+j对应的数值就放在list中，

依次去遍历list即可。

只是这里面要有2个变量，1个是得知道map中key的范围，也就是从0到最下面一个list的末尾的值。我们用math.max()去遍历即可；

另一个变量就是数组的长度，我们在遍历list的时候，用给一个变量去每次保存list的长度即可；

剩下就是将map中的list，根据key值依次放到数组中，但是这里面需要注意的是，

我们遍历的时候，是同一个list，然后list里面的index累加，这时候的顺序正好是反着的，

所以要j--去依次放入对应的数值。

下面就是代码了，有问题可以联系；

Runtime: 41 ms, faster than 72.38% of Java online submissions for Diagonal Traverse II.

Memory Usage: 69.7 MB, less than 55.25% of Java online submissions for Diagonal Traverse II.

难得的有思路就直接过了。。。