1424. Diagonal Traverse II 給你一個二維整數陣列 回傳對角線排序的陣列 Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9] https://assets.leetcode.com/uploads/2020/04/08/sample_1_1784.png Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16] https://assets.leetcode.com/uploads/2020/04/08/sample_2_1784.png Intuition: 一開始我是想用兩個變數startRow跟index去跑兩層迴圈 一直跑到沒有新元素被加進陣列為止 結果這個解法超慢 時間複雜度是O(n^2) Approach: 後來看別人解法 (最近都在抄答案 我好爛) 他們用一個待處裡的序列 從起點[0,0]開始 每次都把處理中元素下面跟右邊的元素加到待處理陣列 這樣就不會一直計算陣列外無意義的資料 TS Code: function findDiagonalOrder (nums: number[][]): number[] { const queue: [number, number][] = [[0, 0]] const result: number[] = [] while (queue.length > 0) { const [i, j] = queue.shift() result.push(nums[i][j]) if (j === 0 && nums[i + 1]?.[j] != null) queue.push([i + 1, j]) if (nums[i]?.[j + 1] != null) queue.push([i, j + 1]) } return result } -- ※ 發信站: 批踢踢實業坊(ptt-web.org.tw), 來自: 114.32.229.33 (臺灣) ※ 文章網址: https://ptt-web.org.tw/Marginalman/M.1700621410.A.30D