二维数组之字形(Zigzag)遍历最优解法及相关学习资源咨询

核心思路 #

• 之字形遍历的本质是按行索引+列索引的和s分组遍历，所有在同一条斜线上的元素的s值完全相同
• 对于s为奇数的斜线，按「行索引从大到小」的顺序取元素
• 对于s为偶数的斜线，按「行索引从小到大」的顺序取元素
• 遍历s的取值范围是0到m+n-2，其中m是矩阵行数，n是矩阵列数
• 每次遍历时注意边界控制，行索引不能小于0、不能超过m-1，列索引不能小于0、不能超过n-1

最优解法代码（JS实现） #

function zigzagTraverse(matrix) {
  const m = matrix.length
  if (m === 0) return []
  const n = matrix[0].length
  const res = []
  // 遍历所有行+列的和s
  for (let s = 0; s <= m + n - 2; s++) {
    if (s % 2 === 1) {
      // 奇数s：行从大到小遍历
      for (let row = Math.min(s, m - 1); row >= Math.max(0, s - n + 1); row--) {
        res.push(matrix[row][s - row])
      }
    } else {
      // 偶数s：行从小到大遍历
      for (let row = Math.max(0, s - n + 1); row <= Math.min(s, m - 1); row++) {
        res.push(matrix[row][s - row])
      }
    }
  }
  return res
}

// 测试示例
const input = [
  ['🍌','🍎','😃','🐉'],
  ['👺','🍺','🍩','🚴'],
  ['🚘','🦑','🚆','🏝'],
  ['🌆','🛹','🕺','🍕']
]
console.log(zigzagTraverse(input)) // 输出与预期完全匹配

复杂度说明 #

• 时间复杂度：O(mn)，每个元素恰好被遍历一次，没有冗余操作，是该问题的理论最优时间复杂度
• 空间复杂度：O(1)（不计入结果存储的开销），仅使用了有限的临时变量

同类问题学习建议 #

这类问题属于矩阵遍历类的经典变种，核心训练方向是坐标规律归纳：

• 遇到陌生的矩阵遍历需求时，先手动列出前几个遍历到的元素的行列坐标，找坐标的共性规律
• 可以针对性练习螺旋矩阵、对角线遍历、顺时针分层遍历等同类矩阵问题，熟练后可以快速总结出任意遍历规则的坐标映射关系

内容的提问来源于stack exchange，提问作者Alan