当前位置：首页 > article >正文

Leetcode 54: 螺旋矩阵

article 2025/3/5 0:39:41

Leetcode 54: 螺旋矩阵 是一道经典的矩阵遍历模拟题目，要求我们以螺旋顺序遍历一个二维数组。这个问题在面试中非常经典，考察模拟、数组操作以及逻辑清晰度。掌握本题的高效解法可以迅速给面试官留下好印象。

适合面试的解法：边界法（层级遍历）

解法描述

核心思想：一次遍历一圈，按四个边界移动指针
- 定义四个边界：top, bottom, left, right，分别表示当前未遍历层的上边界、下边界、左边界和右边界。
- 遍历一圈后，逐步缩小边界范围，直到所有元素都被处理。
边界调整规则：
- 从左到右遍历上侧（top 行），然后 top++；
- 从上到下遍历右侧（right 列），然后 right--；
- 如果还有未遍历的行，则 从右到左遍历底侧（bottom 行），然后 bottom--；
- 如果还有未遍历的列，则 从下到上遍历左侧（left 列），然后 left++。
- 每次遍历完一圈，都缩小边界范围。
终止条件：
- 当 top > bottom 或 left > right 时，说明所有元素都已访问。

代码模板

import java.util.*;

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

        int top = 0, bottom = matrix.length - 1; // 上下边界
        int left = 0, right = matrix[0].length - 1; // 左右边界

        while (top <= bottom && left <= right) {
            // 从左到右遍历上边界
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++; // 上边界缩小

            // 从上到下遍历右边界
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--; // 右边界缩小

            // 检查是否还有未遍历的行
            if (top <= bottom) {
                // 从右到左遍历下边界
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--; // 下边界缩小
            }

            // 检查是否还有未遍历的列
            if (left <= right) {
                // 从下到上遍历左边界
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++; // 左边界缩小
            }
        }

        return result;
    }
}

复杂度分析

时间复杂度：O(m * n)
- 访问每个元素一次，m 为行数，n 为列数。
空间复杂度：O(1)（不计算结果集）
- 原地遍历，无需额外空间。

适用场景

面试首选解法：
- 模拟问题逻辑清晰，层次分明，行为可解释。
- 高效，简单易实现，能快速写出来。
面试中可以结合剪枝优化、边界调整等细节，展示代码能力。

其他解法及分析

解法 2：模拟法

该解法直接按照螺旋的变化顺序（右 -> 下 -> 左 -> 上）模拟移动，通过控制方向实现遍历。

思路

定义方向和边界：
- 使用方向数组 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 表示右、下、左、上的顺序；
- 通过一个 dirIndex 控制当前的方向（如 dirIndex = 0 表示向右，dirIndex = 1 表示向下）。
- 定义已经访问过的区域，并使用二维 visited 数组记录已经访问的元素。
遍历矩阵：
- 从 (0, 0) 点开始，模拟按照当前方向移动；
- 如果即将移动超出边界或者已经访问过，切换到下一个方向；
- 直到所有元素遍历完为止。

代码模板

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

        int m = matrix.length, n = matrix[0].length;
        boolean[][] visited = new boolean[m][n]; // 记录访问情况

        // 定义方向数组（右、下、左、上）
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dirIndex = 0; // 当前方向

        int row = 0, col = 0; // 当前坐标
        for (int i = 0; i < m * n; i++) {
            result.add(matrix[row][col]);
            visited[row][col] = true;

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

            // 如果越界或已经访问过，改变方向
            if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visited[nextRow][nextCol]) {
                dirIndex = (dirIndex + 1) % 4; // 顺时针切换方向
                nextRow = row + dirs[dirIndex][0];
                nextCol = col + dirs[dirIndex][1];
            }

            row = nextRow;
            col = nextCol;
        }

        return result;
    }
}