题目大意：
对角线遍历 II
给你一个列表 nums ，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。
示例 1：
输入：nums = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,4,2,7,5,3,8,6,9]
示例 2：
输入：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]
示例 3：
输入：nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]] 输出：[1,4,2,5,3,8,6,9,7,10,11]
示例 4：
输入：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 个数字。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1424
解题思路分析：
这道题是一道矩阵题目，不过如果我们使用暴力解遍历每一条对角线的话，时间复杂度会达到O(n^2)，由于矩阵的长和宽都是10的5次方数量级，这种算法显然会TLE。仔细观察本题，实际上它是一个不规则的矩阵，也就是说他每一行的长度是不同的，另外题目也给出数字的规模不会超过10的5次方，因此我们需要变换一个角度去思考问题。
首先我们应该将所有的数字进行分组，分组的标准即是他们是否在同一对角线上。判断同一对角线上的数字的方法很简单，即任意位置的横坐标加上纵坐标，值相同的所有点一定在同一对角线上。比如点(2,0),(1,1),(0,2)。
解题时，我们建立一个HashMap，来记录每条对角线的上所有点，key为对角线的id（横坐标加纵坐标），value为该对角线上所有的数字。另外我们要注意一下存储的顺序，由于每条对角线上的数字是从下向上（行数）排列的，因此我们从矩阵的最后一行开始遍历比较好。这样我们能够保证每条对角线上的数字已经按照顺序排列。对于当前行，我们再遍历它的每一列上的数字，使用当前行加上当前列的和，计算出当前数字所属的对角线id，将该数字存入map中对应该id的集合即可。重复此步骤直到循环结束。
另外，对角线的排列是从左至右，也就是他们id的升序排列。我们从0循环至最大id，分别取出map中该对应id的对角线上的所有数字，顺序将其放入返回结果即可。
实现代码：
public int[] findDiagonalOrder(List<List<Integer>> nums) {
// 记录每条对角线上的数字
Map<Integer, List<Integer>> map = new HashMap<>();
// 最大对角线id
int maxId=0;
// 所有节点个数
int size=0;
// 从下向上循环每一行
for(int i=nums.size()-1;i>=0;i--){
// 取出当前行的所有数字
List<Integer> list = nums.get(i);
// 循环当前行的每一个数字
for(int j=0;j<list.size();j++){
// 当前数字所在对角线的id（行加列）
int id = i+j;
// 取得该对角线上的所有数字集合
List<Integer> l = map.getOrDefault(id, new ArrayList<>());
// 将当前数字加入集合
l.add(list.get(j));
// 将集合存入map
map.put(id, l);
// 更新最大对角线id
maxId=Math.max(maxId, id);
// 节点个数加一
size++;
}
}
// 初始化返回数组
int[] res = new int[size];
// 返回结果数组的当前下标
int index=0;
// 循环每一个对角线id
for(int i=0;i<=maxId;i++){
// 取得当前对角线上的所有数字
List<Integer> l = map.get(i);
// 将每个数字按顺序加入返回结果
for(int j=0;j<l.size();j++){
res[index++]=l.get(j);
}
}
return res;
}本题解法执行时间为32ms。
Runtime: 32 ms, faster than 91.28% of Java online submissions for Diagonal Traverse II.
Memory Usage: 74.9 MB, less than 100.00% of Java online submissions for Diagonal Traverse II.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1424-diagonal-traverse-ii-解题思路分析/