每日算法 — 使用java实现螺旋矩阵：顺时针遍历与边界收缩控制

算法背景

螺旋矩阵（Spiral Matrix）是按顺时针方向从外向内逐层遍历或填充二维数组的经典问题。该问题在面试中高频出现，同时也在图像处理（螺旋采样）、游戏开发（螺旋视野渲染）、迷宫生成等领域有实际应用价值。核心挑战在于如何在遍历过程中正确管理边界，避免重复访问或越界。

核心思想

螺旋遍历可以分解为四个方向的重复移动：右 → 下 → 左 → 上。每完成一个方向的遍历，对应边界向内收缩一层（上边界下移、下边界上移、左边界右移、右边界左移）。当边界交错时，遍历结束。使用方向向量可以优雅地实现转向逻辑。

Java实现

import java.util.ArrayList;
import java.util.List;

/**
 * 螺旋矩阵算法实现
 * 支持顺时针遍历、螺旋填充与边界收缩策略
 */
public class SpiralMatrix {

    /**
     * 顺时针螺旋遍历二维矩阵
     * 返回按螺旋顺序排列的元素列表
     */
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        // 定义四个边界
        int top = 0;          // 上边界（已遍历的最上行）
        int bottom = rows - 1; // 下边界（已遍历的最下行）
        int left = 0;         // 左边界（已遍历的最左列）
        int right = cols - 1;  // 右边界（已遍历的最右列）

        while (top <= bottom && left <= right) {
            // 方向1：从左到右遍历上边界
            for (int col = left; col <= right; col++) {
                result.add(matrix[top][col]);
            }
            top++; // 上边界下移

            // 方向2：从上到下遍历右边界
            for (int row = top; row <= bottom; row++) {
                result.add(matrix[row][right]);
            }
            right--; // 右边界左移

            // 方向3：从右到左遍历下边界（需检查是否还有行）
            if (top <= bottom) {
                for (int col = right; col >= left; col--) {
                    result.add(matrix[bottom][col]);
                }
                bottom--; // 下边界上移
            }

            // 方向4：从下到上遍历左边界（需检查是否还有列）
            if (left <= right) {
                for (int row = bottom; row >= top; row--) {
                    result.add(matrix[row][left]);
                }
                left++; // 左边界右移
            }
        }

        return result;
    }

    /**
     * 生成n x n的螺旋填充矩阵
     * 从1开始按顺时针螺旋顺序填充
     */
    public static int[][] generateSpiral(int n) {
        int[][] matrix = new int[n][n];

        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;

        while (top <= bottom && left <= right) {
            // 填充上边界（从左到右）
            for (int col = left; col <= right; col++) {
                matrix[top][col] = num++;
            }
            top++;

            // 填充右边界（从上到下）
            for (int row = top; row <= bottom; row++) {
                matrix[row][right] = num++;
            }
            right--;

            // 填充下边界（从右到左）
            if (top <= bottom) {
                for (int col = right; col >= left; col--) {
                    matrix[bottom][col] = num++;
                }
                bottom--;
            }

            // 填充左边界（从下到上）
            if (left <= right) {
                for (int row = bottom; row >= top; row--) {
                    matrix[row][left] = num++;
                }
                left++;
            }
        }

        return matrix;
    }

    /**
     * 使用方向向量实现螺旋遍历
     * 更通用的实现，适用于任意起始方向和转向规则
     */
    public static List<Integer> spiralOrderWithDirection(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        // 访问标记矩阵
        boolean[][] visited = new boolean[rows][cols];

        // 方向向量：右、下、左、上（顺时针）
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dirIndex = 0; // 当前方向索引

        int row = 0, col = 0;

        for (int i = 0; i < rows * cols; i++) {
            result.add(matrix[row][col]);
            visited[row][col] = true;

            // 计算下一个位置
            int nextRow = row + directions[dirIndex][0];
            int nextCol = col + directions[dirIndex][1];

            // 如果下一个位置越界或已访问，则转向
            if (nextRow < 0 || nextRow >= rows || nextCol < 0 || 
                nextCol >= cols || visited[nextRow][nextCol]) {
                dirIndex = (dirIndex + 1) % 4; // 顺时针转向
                nextRow = row + directions[dirIndex][0];
                nextCol = col + directions[dirIndex][1];
            }

            row = nextRow;
            col = nextCol;
        }

        return result;
    }

    /**
     * 逆时针螺旋遍历矩阵
     */
    public static List<Integer> spiralOrderCounterClockwise(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean[][] visited = new boolean[rows][cols];

        // 方向向量：右、上、左、下（逆时针）
        int[][] directions = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
        int dirIndex = 0;
        int row = rows - 1, col = 0; // 从左下角开始

        for (int i = 0; i < rows * cols; i++) {
            result.add(matrix[row][col]);
            visited[row][col] = true;

            int nextRow = row + directions[dirIndex][0];
            int nextCol = col + directions[dirIndex][1];

            if (nextRow < 0 || nextRow >= rows || nextCol < 0 || 
                nextCol >= cols || visited[nextRow][nextCol]) {
                dirIndex = (dirIndex + 1) % 4;
                nextRow = row + directions[dirIndex][0];
                nextCol = col + directions[dirIndex][1];
            }

            row = nextRow;
            col = nextCol;
        }

        return result;
    }

    /**
     * 打印矩阵
     */
    public static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            for (int val : row) {
                System.out.printf("%3d ", val);
            }
            System.out.println();
        }
    }

    /**
     * 按层打印矩阵（从外到内每层分别输出）
     */
    public static List<List<Integer>> getLayers(int[][] matrix) {
        List<List<Integer>> layers = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return layers;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int top = 0, bottom = rows - 1;
        int left = 0, right = cols - 1;

        while (top <= bottom && left <= right) {
            List<Integer> layer = new ArrayList<>();

            // 上边界
            for (int col = left; col <= right; col++) {
                layer.add(matrix[top][col]);
            }
            // 右边界（不含拐角）
            for (int row = top + 1; row <= bottom; row++) {
                layer.add(matrix[row][right]);
            }
            // 下边界（不含拐角，且需与上边界不同行）
            if (top < bottom) {
                for (int col = right - 1; col >= left; col--) {
                    layer.add(matrix[bottom][col]);
                }
            }
            // 左边界（不含拐角，且需与右边界不同列）
            if (left < right) {
                for (int row = bottom - 1; row > top; row--) {
                    layer.add(matrix[row][left]);
                }
            }

            layers.add(layer);
            top++;
            bottom--;
            left++;
            right--;
        }

        return layers;
    }

    public static void main(String[] args) {
        System.out.println("=== 螺旋遍历示例 ===");
        int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };

        System.out.println("原始矩阵:");
        printMatrix(matrix);

        System.out.println("\n顺时针螺旋遍历结果:");
        System.out.println(spiralOrder(matrix));

        System.out.println("\n方向向量法遍历结果:");
        System.out.println(spiralOrderWithDirection(matrix));

        System.out.println("\n=== 螺旋填充示例 ===");
        int[][] spiral = generateSpiral(5);
        System.out.println("5x5 螺旋填充矩阵:");
        printMatrix(spiral);

        System.out.println("\n=== 非正方形矩阵遍历 ===");
        int[][] rectMatrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9},
            {10, 11, 12}
        };
        System.out.println("4x3 矩阵:");
        printMatrix(rectMatrix);
        System.out.println("螺旋遍历: " + spiralOrder(rectMatrix));

        System.out.println("\n=== 按层分解 ===");
        List<List<Integer>> layers = getLayers(matrix);
        for (int i = 0; i < layers.size(); i++) {
            System.out.println("第 " + (i + 1) + " 层: " + layers.get(i));
        }
    }
}

复杂度分析

算法优势与适用场景

优势：
– 边界收缩法空间复杂度为 $O(1)$，极为高效
– 方向向量法易于扩展至任意转向规则
– 代码清晰，四种方向对称处理

适用场景：
– 面试高频考点（字节、腾讯、阿里均曾考察）
– 图像处理的螺旋采样与卷积
– 游戏中的视野渲染与地图探索
– 矩阵按优先级处理（外层优先）