動機

reverse是好東西

Problem

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

 

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:

    t
  • m == mat.length
  • t
  • n == mat[i].length
  • t
  • 1 <= m, n <= 104
  • t
  • 1 <= m * n <= 104
  • t
  • -105 <= mat[i][j] <= 105

Sol

從右上方的點出發,需要時再reverse

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        ret,rev = [], True
        for (i,j) in [(0,x) for x in range(len(mat[0]))][:-1]+[(x,len(mat[0])-1) for x in range(len(mat))]:
            tmp, x = [], 0
            while i+x < len(mat) and j-x >= 0:
                tmp.append(mat[i+x][j-x])
                x += 1
            
            if rev:
                ret += tmp[::-1]
            else:
                ret += tmp
            rev = not rev
        return ret