全栈开发知识库

35.螺旋矩阵

题目

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1:
image

  • 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
  • 输出：[1,2,3,6,9,8,7,4,5]

示例 2:
image

  • 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
  • 输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

思路

  • 对于这种螺旋遍历的方法，重要的是要确定上下左右四条边的位置
  • 初始化的时候，上边up就是0，下边down就是m-1，左边left是0，右边right是n-1。
  • 然后我们进行while循环
    • 先遍历上边第一行up ，将所有元素加入结果res，然后上边下移一位，如果此时上边大于下边，说明此时已经遍历完成了，直接break。
class Solution {
    fun spiralOrder(matrix: Array<IntArray>): List<Int> {
        val result = mutableListOf<Int>()
        if (matrix.isEmpty() || matrix[0].isEmpty()) {
            return result
        }

        var top = 0
        var bottom = matrix.size - 1
        var left = 0
        var right = matrix[0].size - 1

        while (top <= bottom && left <= right) {
            // ① 上边：从左到右
            for (col in left..right) {
                result.add(matrix[top][col])
            }
            top++

            // ② 右边：从上到下
            for (row in top..bottom) {
                result.add(matrix[row][right])
            }
            right--

            // ③ 下边：从右到左（需确认还有未走的行）
            if (top <= bottom) {
                for (col in right downTo left) {
                    result.add(matrix[bottom][col])
                }
                bottom--
            }

            // ④ 左边：从下到上（需确认还有未走的列）
            if (left <= right) {
                for (row in bottom downTo top) {
                    result.add(matrix[row][left])
                }
                left++
            }
        }

        return result
    }
}

最易错的点：为什么步骤 ③ ④ 要加 if 判断？

这是本题唯一的坑，必须理解。

在步骤 ① ② 执行后，top 和 right 已经收缩了。

对于非正方形矩阵或走到最内层时，可能出现「上下边界已交错，但代码还在试图走下边/左边」的重复访问。

举个例子：单行矩阵 [[1, 2, 3]]（1 行 3 列）:

  • 初始：top=0, bottom=0, left=0, right=2

  • ① 上边 left→right：访问 1,2,3，然后 top++ → top=1

  • ② 右边 top→bottom：top(1) > bottom(0)，循环不执行，right-- → right=1
  • ③ 下边：if (top <= bottom)? → 1 <= 0 为 false，跳过 ✅ 如果不加这个 if，会从 right(1) 倒着走 matrix[0][1]、matrix[0][0] → 重复访问 2 和 1！❌

所以步骤 ③ 必须确认 top <= bottom（还有没走的行），步骤 ④ 必须确认 left <= right（还有没走的列）。步骤 ① ② 不用判断，因为 while 入口已经保证了它们成立。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res=new ArrayList<Integer>();

        if(matrix.length==0 || matrix[0].length==0) {
            return res;
        }

        int m = matrix.length;
        int n =matrix[0].length;

        int up = 0;
        int down = m-1;
        int left = 0;
        int right = n-1;

        while(true) {
            for(int i=left; i<=right; i++) {
                res.add(matrix[up][i]);
            }

            if (++up > down) {
                break;
            }

            for (int i = up; i <= down; i++) {
                res.add(matrix[i][right]);
            }

            if (--right < left) {
                break;
            }

            for (int i = right; i >= left; i--) {
                res.add(matrix[down][i]);
            }

            if (--down < up) {
                break;
            }

            for (int i = down; i >= up; i--) {
                res.add(matrix[i][left]);
            }

            if (++left > right) {
                break;
            }
        }
        return res;
    }
}

-下一题

  • 邮箱 ：charon.chui@gmail.com
  • Good Luck!