题目

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++，当我们移动到最后一列时没法再继续移动列，所以向下移动一行。而还没到最后一列时，我们继续移动一列
而对于方向向下则与之相反。

代码实现

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

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;
	}
}

总结

代码实现起来其实很简答。难的是在对这个对角线遍历的建模。
如何把自己直觉式的解决方法转化成计算机能执行的代码是相当不容易的。
而从这道题中，我觉得将大问题分解成小问题再逐个击破是一个很好的方法~