LeetCode 498. Diagonal traversal

Title Description ：

Give you a size of m x n Matrix mat , Please traverse diagonally , Use an array to return all the elements in the matrix .

Example ：

 Input ：mat = [[1,2,3],[4,5,6],[7,8,9]]
 Output ：[1,2,4,7,5,3,6,8,9]

Ideas ：

A matrix , Let's assume that there is n That's ok ,m Column , Then its diagonal （ refer to / The diagonal of this direction , instead of \） Altogether n + m - 1 strip . Suppose the diagonal number is from 0 Start , Then the number range of all diagonals is [0,n + m - 2], And it's easy to get a property , The number is i Point on the diagonal of , The sum of the horizontal and vertical coordinates is equal to i.

We can see from the sample data ： Number i Is an even number of diagonals , The traversal direction is from bottom left to top right ; Number i Is the diagonal of an odd number , The traversal direction is from top right to bottom left .

From bottom left to top right , The change in the coordinates of a point is , The number of rows minus 1, The number of columns plus 1. namely x--,y++

From top right to bottom left , The change in the coordinates of a point is , Number of rows plus 1, Subtract the number of columns 1,. namely x++,y--

When a diagonal traversal is complete , We need to find the next point as a starting point , And flip the traversal direction .

Find the next point as the starting point , It can be discussed in different situations .

Set the number of the diagonals currently traversed as i

• When the direction is from bottom left to top right
  • When i < m - 1 when , Next starting column , It must be i + 1, namely y = i + 1, Go ahead , It can be directly based on the fact that the abscissa and ordinate of all points on the diagonal are constants , To figure it out , namely x = (i + 1) - y
  • When i >= m - 1 when , Next starting column , Only to the last column , namely y = m - 1, and x = (i + 1) - y
• When the direction is from top right to bottom left
  • When i < n - 1 when , Next starting line , It must be i + 1, namely x = i + 1, and y = (i + 1) - x
  • When i >= n - 1 when , Next starting line , Only to the last line , namely x = n - 1, and y = (i + 1) - x

class Solution {
    
    //  Important nature :  Points on the same diagonal ,  Its [x,y] The sum of the coordinates is fixed 
    //  Number of diagonal lines ,  in total  m + n - 1  strip 
    //  The first  i  The sum of the coordinates on the diagonal lines is  i
    //  Sum is even ,  Go to the upper right corner  (x--, y++)
    //  Sum is odd ,  Go to the lower left corner  (x++, y--)
    public int[] findDiagonalOrder(int[][] mat) {
    
        int n = mat.length, m = mat[0].length;
        int[] ans = new int[n * m];
        int k = 0;
        int x = 0, y = 0;
        for (int i = 0; i < n + m - 1; i++) {
    
           if ((i & 1) == 0) {
    
               //  Take this line to the end 
               while (x >= 0 && y < m) ans[k++] = mat[x--][y++];
               if (i < m - 1) y = i + 1;
               else y = m - 1;
               x = i + 1 - y;
           } else {
    
               while (x < n && y >= 0) ans[k++] = mat[x++][y--];
               if (i < n - 1) x = i + 1;
               else x = n - 1;
               y = i + 1 - x;
           }
        }
        return ans;
    }
}