# Leetcode 498. Diagonal Traverse 練習
> Difficulty : `Medium`
> `Java` `演算法Algorithm`

> 撰寫人[name=KVJK_2125] [time=Fri, Mar 29, 2024 16:00]

## 題目
### 說明 Description
原文：`Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.`
翻譯：給一個 m x n 的矩陣mat，回一個以對角線遍歷，並包含該陣列所有元素的陣列。

### 範例 Example
Example 1:
> Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:
>Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

### 限制條件 Constraints
- `m == mat.length`
- `n == mat[i].length`
- `1 <= m, n <= 104`
- `1 <= m * n <= 104`
- `-105 <= mat[i][j] <= 105`

## 解題
### 思路 Intuition/Approach
以Example 1做解釋：
- Step1.<br> 先標注出xy軸：<br>

- Step2.<br> 記下輸出時的xy順序以及走訪方向：<br>- 第1次對角線走訪：`右上` `(0,0)` <br>- 第2次對角線走訪：`左下` `(0,1)(1,0)` <br>- 第3次對角線走訪：`右上` `(2,0)(1,1)(0,2)` <br>- 第4次對角線走訪：`左下` `(1,2)(2,1)` <br>- 第5次對角線走訪：`右上` `(2,2)` <br>

- Step3.<br> 發現在第3次時，x走訪順序為2 --> 1 --> 0 由大到小；<br>而第2、4次時，x走訪順序為0 --> 1 --> 2 由小到大。<br>建立一個計次變數`count = 1`，在奇數次數時，反轉陣列再儲存。

- Step4.<br> 要創建兩個ArrayList：<br>一個用作走訪對角線，並進行判斷反轉；<br>一個用作儲存可輸出的結果。

- Step5.<br>因為Step3.的'拿取後反轉'，可統一走訪方式為'右上至左下'。<br>及每次走訪路線均為`(++, --)`。

- Step6.<br> 建立`int x = 0`以及`int y = 0`：<br>x會累加至row走訪完，<br>y會計算至col走訪完。<br>建立`int i = x`以及`int j = y`在走訪迴圈內：<br>用於計算被統一的走訪方式，寫作`i++`以及`j--`。<br>當 `y > col`時，即 x不會再出現0，<br>於是`x++`，且`y = col`並繼續。直到`x >= row`且`y >= col`。
### 程式碼 Code（加註解）

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        ArrayList<Integer> list = new ArrayList<>();    //用來存放最後結果的陣列
        int row = mat.length-1; //row
        int col = mat[0].length-1;  //col
        int x = 0, y = 0, count = 1;
        while(x<=row && y<=col){
            int i = x;
            int j = y;
            //在迴圈內建立一個新的ArrayList，在新一輪的xy中，用來遇到x為0時reverse
            ArrayList<Integer> get = new ArrayList<>();
            while(i>=0 && i<=row && j>=0){
                get.add(mat[i][j]); //加入陣列
                //向左上移動
                i++;    //向右
                j--;    //向上
            }
            //如果是在第奇數次數走訪，則反轉該次陣列
            if(count%2 != 0){
                Collections.reverse(get);
            }
            
            list.addAll(get);
            count++;    //次數++
            y++;    
            //在y大於col時，表示x不會再是0
            if(y>col){
                x++;    //x必須+1
                y = col;    //y最大就是col
            }
        }
        //沒有在Leetcode、沒有另外用class，可以用這個直接輸出
        //System.out.println(list);
        
        //Leetcode因為另外用了class，所以必須return相同型態的變數
        //建立一個與一開始傳入的陣列相同的變數，並以該陣列回傳
        int [] ans = new int[(row+1)*(col+1)];
        int size = 0;
        for(int i: list){
            ans[size++] = i;
        }
        //System.out.println("the output about that mat do Diagonal Traverse : \n" + ans) ;
        return ans;
    }
}