package com.zmz.algorithm.array;

import java.util.Arrays;

/**
 * @author 张明泽
 * Create by 2022/5/25 11:32
 * 对角线遍历
 * LeetCode-498
 */
public class DiagonalTraversal {
    public static void main(String[] args) {
        int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};
        int[] result = findDiagonalOrder2(arr);
        System.out.println(Arrays.toString(result));
    }
    /**
     * 简单易懂版 - 画两个图 - 看边界
     */
    /**
     * 考虑边界
     * 偶数的对角线都在上面拐所以考虑是否在第一行(除了第一行最后一个 单独考虑）
     * 奇数的对角线都在下面拐所以考虑是否在第一列(除了第一列最后一个 单独考虑)
     */
    public static int[] findDiagonalOrder2(int[][] arr) {
       int row = arr.length;
       int col = arr[0].length;
       int x = 0;
       int y = 0;
       int index = 0;
       int[] res = new int[row * col];
       while (index < row * col) {
           res[index++] = arr[x][y];
           // 对角线是偶数 往上走
           if ((x + y) % 2 == 0) {
               // 先判断是否越界(右上角)
               if (y == col - 1) {
                   x++;
               } else if ( x == 0) { // 是否在第一行
                   y++;
               } else { // 正常情况
                   x--;
                   y++;
               }
           } else {
               if ( x == row - 1) { // 左下角
                   y++;
               } else if (y == 0) { // 是否在第一列
                   x++;
               } else {
                   x++;
                   y--;
               }
           }
       }
       return res;
    }
}