【LeetCode】螺旋矩阵

题目

题目链接

请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素，示例如下：

思路

整体思路为模拟。具体地，可以采用“减而治之”的思想，将整个遍历过程拆分为一次次对每一行和每一列的遍历，每次只考虑一行/一列，每完成一次遍历矩阵整体会收缩一行/一列，此时更新相应的边界坐标即可。
一共有四个方向的遍历顺序，需要分别处理。

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(n)

代码

const enum EDirection {
    right,
    down,
    left,
    up,
}

function spiralOrder(matrix: number[][]): number[] {
    const result: number[] = [];
    const m = matrix.length;
    const n = matrix[0].length;

    // 递归地访问每一行或列
    const visit = (rowStart: number, rowEnd: number, colStart: number, colEnd: number, direction: EDirection) => {
        if (rowStart === rowEnd || colStart === colEnd) return;

        // 枚举每个方向push元素的顺序
        switch (direction) {
            case EDirection.right: {
                for (let i = colStart; i < colEnd; i++) {
                    result.push(matrix[rowStart][i]);
                }
                visit(rowStart + 1, rowEnd, colStart, colEnd, EDirection.down);
                break;
            }
            case EDirection.down: {
                for (let i = rowStart; i < rowEnd; i++) {
                    result.push(matrix[i][colEnd- 1]);
                }
                visit(rowStart, rowEnd, colStart, colEnd - 1, EDirection.left);
                break;
            }
            case EDirection.left: {
                for (let i = colEnd - 1; i >= colStart; i--) {
                    result.push(matrix[rowEnd - 1][i]);
                }
                visit(rowStart, rowEnd - 1, colStart, colEnd, EDirection.up);
                break;
            }
            case EDirection.up: {
                for (let i = rowEnd - 1; i >= rowStart; i--) {
                    result.push(matrix[i][colStart]);
                }
                visit(rowStart, rowEnd, colStart + 1, colEnd, EDirection.right);
                break;
            }
        }
    }
    // 从原始矩阵开始
    visit(0, m, 0, n, EDirection.right);
    return result;
};