498. 對角線遍歷

給定一個含有 M x N 個元素的矩陣（M 行，N 列），請以對角線遍歷的順序返回這個矩陣中的所有元素，對角線遍歷如下圖所示。

示例:

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

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

解釋:

說明:

給定矩陣中的元素總數不會超過 100000 。

解題思路

對于如下矩陣，我們以矩陣上邊界和右邊界的點作為起點開始遍歷，我們統一以左下方為方向進行遍歷

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

但是題目中顯然是存在左下方遍歷和右上方遍歷交替進行的，但是問題在于他們的起點難以確定，所以我們統一以左下方為基準，后面再對元素進行翻轉

代碼

class Solution {public int[] findDiagonalOrder(int[][] mat) {int n=mat.length,m=mat[0].length;int[] res = new int[n * m];int p=0;boolean pos=false;for (int i=0;i<m;i++){int x=0,y=i,l=p;while (x>=0&&x<n&&y>=0&&y<m){ res[p++]=mat[x][y];x++;y--;}       int r=p-1;if(!pos){while (l<r){int t=res[l];res[l]=res[r];res[r]=t;l++;r--;}}pos=!pos;}for (int i=1;i<n;i++){int x=i,y=m-1,l=p;while (x>=0&&x<n&&y>=0&&y<m){res[p++]=mat[x][y];x++;y--;}int r=p-1;if(!pos){while (l<r){int t=res[l];res[l]=res[r];res[r]=t;l++;r--;}}pos=!pos;}return res;}
}