[leetcode] 54. 螺旋矩阵

题目描述

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

示例 1：

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

示例 2：

输入：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

解题方法

模拟

这道题和第48题有点类似，都是按照不同的方式进行矩阵遍历模拟。

我说一下具体思路，我们可以设置四个点，sr在左上角，er在右上角，sc在左下角，ec在右下角。每次遍历时，我们先从sr往右遍历到er，再由er往下遍历到ec，再由ec往左遍历到sc，再由sc往上遍历到sr。遍历完一圈后，我们再把sr、er、sc、ec往内缩一格，然后按照上面的方式继续遍历。直到sr、er、sc、ec缩到最内层时，遍历完成。

java代码

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> list = new ArrayList<Integer>();
    if (matrix == null || matrix.length == 0) {
        return list;
    }
    // 起始行
    int sr = 0;
    // 起始列
    int sc = 0;
    // 结束行
    int er = matrix.length - 1;
    // 结束列
    int ec = matrix[0].length - 1;
    while (sr <= er && sc <= ec) {
        // 起始行、起始列、结束行、结束列在同一位置，只剩最后一个元素
        if (sr == er && sc == ec) {
            list.add(matrix[sr][sc]);
            break;
        }
        // 起始行等于结束行，起始列小于结束列，还剩最后一列需要遍历
        if (sr == er && sc < ec) {
            for (int i = sc; i <= ec; i++) {
                list.add(matrix[sr][i]);
            }
            break;
        }
        // 起始列等于结束列，起始行小于结束行，还剩最后一行需要遍历
        if (sr < er && sc == ec) {
            for (int i = sr; i <= er; i++) {
                list.add(matrix[i][sc]);
            }
            break;
        }
        // 其余情况，按照右、下、左、上的顺序遍历
        for (int i = sc; i < ec; i++) {
            list.add(matrix[sr][i]);
        }
        for (int i = sr; i < er; i++) {
            list.add(matrix[i][ec]);
        }
        for (int i = ec; i > sc; i--) {
            list.add(matrix[er][i]);
        }
        for (int i = er; i > sr; i--) {
            list.add(matrix[i][sc]);
        }
        // 每遍历完一圈，起始行、起始列、结束行、结束列往内缩一格
        sr++;
        sc++;
        er--;
        ec--;
    }
    return list;
}

复杂度分析

时间复杂度：$O(N)$，需要遍历一次矩阵。
空间复杂度：$O(1)$，只有几个变量存储。

相似题目

[leetcode] 48. 旋转图像