题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

https://leetcode-cn.com/problems/spiral-matrix/

解法1

我们首先举3个例子来分析如何实现矩阵的螺旋顺序遍历. 我们分别以3×3, 3×4与4×3的矩阵为例.

我们将遍历步骤分为水平从左到右遍历、垂直从上向下遍历、水平从右向左遍历与垂直从下向上遍历。如果遇到内部只包含一行或一列的情况，那么就全部遍历该行或列。

上面只是大概思路。当时现实时，我们会遇到另一个问题：“按照环形遍历几圈结束”？如果我们多举几个例子，可以容易地推测“圈数=ceil(max(row, col)/2)”. 另一个问题：“每一圈的起点是如何计算的？”我们可以从图上看出，每次我轮都从（0，0）、（1，1）、（2，2）……为起点遍历的。因此，我们取（round，round）作为遍历的起点。我们记当前的行号列号为（row，col），如果水平向右就遍历matrix[row][col++]，如果垂直向下就遍历matrix[row++][col]以此类推。经过上面的分析，我们就能编写出矩阵按照螺旋遍历的代码了。

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

        if (matrix == null || matrix.length == 0) 
            return res;


        int nRow = matrix.length, nCol = matrix[0].length;
        int nRound = (int) Math.ceil(Math.min(nRow, nCol) / 2.0);

        for (int round = 0; round < nRound; round++) {
            int row = round, col = round;

            // 内部只包含一行
            if (nRow - 2 * round == 1) {
                for (int i = 0; i < nCol - 2 * round; i++)
                    res.add(matrix[row][col++]);
                break;
            } else if (nCol - 2 * round == 1) { // 内部只包含一列
                for (int i = 0; i < nRow - 2 * round; i++)
                    res.add(matrix[row++][col]);
                break;
            }

            // -->
            for (int i = 0; i < nCol - 2 * round - 1; i++)
                res.add(matrix[row][col++]);


            // |
            // |
            // V
            for (int i = 0; i < nRow - 2 * round - 1; i++)
                res.add(matrix[row++][col]);

            // <--
            for (int i = 0; i < nCol - 2 * round - 1; i++)
                res.add(matrix[row][col--]);

            // ^
            // |
            // |
            for (int i = 0; i < nRow - 2 * round - 1; i++)
                res.add(matrix[row--][col]);
        }

        return res;
    }
}