螺旋矩阵

54. 螺旋矩阵

本题是矩阵相关模拟题目中非常有意思且经典的一道高频面试题。

一个较为直观且容易理解的做法是四边界法。

四边界法，顾名思义，就是利用四个变量： top 、bottom、left、right 维护 “尚未遍历的矩形区域” ，它们分别代表上下左右这四个方位的边界。

初始时，top = 0、bottom = matrix.length - 1、left = 0、right = matrix[0].length - 1，即上下边界和左右边界的下标范围均采用闭区间表示法。

要按照顺时针螺旋遍历矩阵元素，其实就是依次顺着遍历上边界 → 右边界 → 下边界 → 左边界，每遍历完一条边，就将对应边界向内收缩，直到待遍历区域为空。

综上所述。这一流程可以归纳总结为以下伪代码：

▼
text
复制代码
初始化边界：top 、bottom、left、right；

当 边界合法（即left <= right && top <= bottom）:
	从左往右遍历上边界;
	top++;
	从上往下遍历右边界;
	right--;
	从右往左遍历下边界;
	bottom--;
	从下往上遍历左边界;
	left++;

具体实现时，需要注意边界收缩后，剩余区域可能已经为空。因此，除了通过外层循环判断整个矩形区域是否还有元素，还要在必要时检查对应方向的边界是否合法，避免重复遍历或访问已经不属于待遍历区域的元素。

参考实现如下：

▼
java
复制代码
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
    while (left <= right && top <= bottom) {
        // 从左往右遍历上边界
        for (int j = left; j <= right; j++) {
            result.add(matrix[top][j]);
        }
        top++;
        // 从上往下遍历右边界
        for (int i = top; i <= bottom ; i++) {
            result.add(matrix[i][right]);
        }
        right--;
        // 从右往左遍历下边界
        // 之前收缩过上边界后，剩余区域可能已经没有行，因此遍历下边界前需要判断 top <= bottom
        if (top <= bottom) {
            for (int j = right; j >= left ; j--) {
                result.add(matrix[bottom][j]);
            }
            bottom--;
        }
        // 从下往上遍历左边界
        // 之前收缩过右边界后，剩余区域可能已经没有列，因此遍历左边界前要额外判断 left <= right
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result.add(matrix[i][left]);
            }
            left++;
        }
    }
    return result;
}

掌握这一思路后，如果面试时面试官临时改成逆时针遍历一个矩阵，你也可以利用同样的思路解决这一问题。