题目

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

思考

最初在纸上写写画画试了很多想法，但都没能解决，真的。。太弱了T T。
后来在YT上看了个印度老哥的题解才醍醐灌顶。在此尝试复述他的题解。

这题就是说将一个二维矩阵按照对角线的形式遍历。

其实输出什么内容直觉很快就能反应过来。
但真正困难的地方在于如何将这个对角线的输出过程具体描述出来。
包括如何确定移动的方向？如何移动？在什么条件下要移向下一行对角线？
如果能将这道题分解为上述三个小问，解题难度则会下降很多。

确定移动方向

移动方向很简单，无非就是向上和向下，可以用一个flag判断上下。

对角线中移动的过程

那么这个对角线移动具体是怎么移动的呢？
我们可以参考example1这个图：
假设我们现在在 '7'，接下来要移动到 '5'，那就是(3,1) -> (2,2)
假设我们在 '6'，接下来要移动到 '8'，那就是(2,3) -> (3,2)
用这两个向上、向下的例子我们可以看出向上就意味着row--, col++（向上一行，向右一列），向下则反过来 row++, col--（向下一行，向左一列）。

移动到下一条对角线

对于怎样移动到下一条对角线，第一直觉肯定是“当碰到边界时就向下一条对角线移动”
这是个很好的直觉
我们可以在这个直觉的基础上细化思考“怎样定义边界条件？”“怎样移动到下一条对角线？”

边界条件

看图我们可以总结出：在row, col加加减减的过程中，当他们超过了m或者n就换行了。
但很明显，这个边界条件是分上下方向的，非常简单却不能忽略。
向上：row < m || col > n - 1
向下：col < n || row > m - 1

向下一条对角线移动

实际上是一条对角线的终点移动到下一条对角线的起点。
对于方向向上：
移动过程是row--, col++，当我们移动到最后一列时没法再继续移动列，所以向下移动一行。而还没到最后一列时，我们继续移动一列
而对于方向向下则与之相反。

代码实现

上面的问题都分析清楚后，就可以写题解了

#Java
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
	//首先判断矩阵为0的情况
	if (mat.length == 0 || mat[0].length == 0) return new int[0];
	//初始化
	int m = mat.length; //矩阵行长度
	int n = mat[0].length; //矩阵列长度
	int[] arr = new int[m*n]; //存对角遍历结果的数组
	int i = 0; //数组的计数
	boolean up = true; //判定方向的flag
	int row = 0, col = 0; //定义当前指向的矩阵位置，从(0,0)开始
	while (row < m && col < n) {
		//方向向上
		if (up) {
		//移动
		while (row > 0 || col < n - 1) {
			arr[i++] = mat[row][col];
			row--;
			col++;
		}
		//移动到边界时会跳出循环，但边界数字还是要压入数组中
		arr[i++] = mat[row][col];
		//同时判断边界情况，是否到达了最后一列
		if (col == n - 1) {
			row++;
		} else {
			col++;
		}
		} else {
		while (col > 0 || row < m - 1) {
			arr[i++] = mat[row][col];
			row++;
			col--;
		}
		arr[i++] = mat[row][col];
		//判断边界情况，是否到达最后一行
		if (row = m - 1) {
			col++;
		} else {
			row++;
		}
		}
		//换到下一条对角线时，方向要变化
		up = !up;
	}
	return arr;
	}
}