[LeetCode] 54. Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

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

螺旋矩阵。

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

思路

这个题没有什么比较巧妙的思路，只能照着遍历的方式去实现了代码，按照右 - 下 - 左 - 上的顺序去遍历。这个题做的时候需要用几个变量去记录二维数组坐标的边界，同时记得当每一行/列遍历完了之后，边界值需要减1因为遍历的时候每一圈的 size 都在减小。

复杂度

时间O(mn)
空间O(n) - 输出是一个一维数组

代码

Java实现

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        // corner case
        if (matrix == null || matrix.length == 0) {
            return res;
        }

        // normal case
        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            // left to right
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            top++;

            // top to bottom
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--;

            // right to left
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    res.add(matrix[bottom][i]);
                }
                bottom--;
            }

            // bottom to top
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    res.add(matrix[i][left]);
                }
                left++;
            }
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
    let res = [];
    if (matrix.length === 0) {
        return res;
    }
    let rowBegin = 0;
    let rowEnd = matrix.length - 1;
    let colBegin = 0;
    let colEnd = matrix[0].length - 1;

    while (colBegin <= colEnd && rowBegin <= rowEnd) {
        // right
        for (var i = colBegin; i <= colEnd; i++) {
            res.push(matrix[rowBegin][i]);
        }
        rowBegin++;

        // down
        for (var i = rowBegin; i <= rowEnd; i++) {
            res.push(matrix[i][colEnd]);
        }
        colEnd--;

        // left
        if (rowBegin <= rowEnd) {
            for (var i = colEnd; i >= colBegin; i--) {
                res.push(matrix[rowEnd][i]);
            }
        }
        rowEnd--;

        // up
        if (colBegin <= colEnd) {
            for (var i = rowEnd; i >= rowBegin; i--) {
                res.push(matrix[i][colBegin]);
            }
        }
        colBegin++;
    }
    return res;
};