螺旋矩阵

📋 算法简介

螺旋矩阵是一个经典的二维数组遍历问题，要求按照螺旋顺序（通常是顺时针）遍历矩阵中的所有元素。这个问题在算法面试中经常出现，是考查数组操作、边界控制和逻辑思维的重要题目。

问题定义

给定一个 m × n 的矩阵，按照螺旋顺序返回矩阵中的所有元素。螺旋顺序是指从矩阵的左上角开始，按照 右 → 下 → 左 → 上 的方向依次遍历，直到访问完所有元素。

示例：

输入矩阵：
[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

螺旋遍历结果：[1, 2, 3, 6, 9, 8, 7, 4, 5]

🎯 问题分析

核心思路

螺旋遍历的关键在于边界控制和方向转换：

1. 边界维护：维护四个边界（上、下、左、右）
2. 方向控制：按照固定顺序改变遍历方向
3. 终止条件：当所有元素都被访问时停止

关键难点

• 正确处理边界条件
• 避免重复访问元素
• 处理特殊情况（单行、单列、空矩阵）

🔧 算法原理

方法一：边界控制法

核心思想： 维护四个边界变量，每完成一个方向的遍历就收缩对应的边界。

算法步骤：

1. 初始化四个边界：top = 0, bottom = m-1, left = 0, right = n-1
2. 按照 右→下→左→上 的顺序遍历
3. 每完成一个方向，收缩对应边界
4. 重复直到 top > bottom 或 left > right

图解过程：

初始状态：        第一轮右移：      第一轮下移：
top=0             top=0            top=1
[1, 2, 3] ←right  [✓, ✓, ✓]        [✓, ✓, ✓]
[4, 5, 6]         [4, 5, 6] ←right [4, 5, ✓]
[7, 8, 9]         [7, 8, 9]        [7, 8, ✓]
bottom=2          bottom=2         bottom=2
left=0 right=2    left=0 right=2   left=0 right=1

方法二：方向数组法

核心思想： 使用方向数组控制移动方向，遇到边界或已访问元素时转向。

算法步骤：

1. 定义方向数组：directions = [[0,1], [1,0], [0,-1], [-1,0]]（右、下、左、上）
2. 使用 visited 数组标记已访问元素
3. 按当前方向移动，遇到障碍时转向
4. 重复直到所有元素被访问

💻 代码实现

Java实现

方法一：边界控制法

public class SpiralMatrix {
    /**
     * 螺旋遍历矩阵 - 边界控制法
     * 时间复杂度：O(m*n)
     * 空间复杂度：O(1) 不计算结果数组
     */
    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;    // 行数
        int n = matrix[0].length; // 列数
        
        // 定义四个边界
        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;
        
        while (top <= bottom && left <= right) {
            // 1. 从左到右遍历上边界
            for (int j = left; j <= right; j++) {
                result.add(matrix[top][j]);
            }
            top++; // 上边界下移
            
            // 2. 从上到下遍历右边界
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--; // 右边界左移
            
            // 3. 从右到左遍历下边界（如果还有行）
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    result.add(matrix[bottom][j]);
                }
                bottom--; // 下边界上移
            }
            
            // 4. 从下到上遍历左边界（如果还有列）
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++; // 左边界右移
            }
        }
        
        return result;
    }
}

方法二：方向数组法

public class SpiralMatrixDirection {
    /**
     * 螺旋遍历矩阵 - 方向数组法
     * 时间复杂度：O(m*n)
     * 空间复杂度：O(m*n) 需要visited数组
     */
    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;
        int n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        
        // 方向数组：右、下、左、上
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 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 + directions[directionIndex][0];
            int nextCol = col + directions[directionIndex][1];
            
            // 检查是否需要转向
            if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || 
                visited[nextRow][nextCol]) {
                directionIndex = (directionIndex + 1) % 4; // 转向
                nextRow = row + directions[directionIndex][0];
                nextCol = col + directions[directionIndex][1];
            }
            
            row = nextRow;
            col = nextCol;
        }
        
        return result;
    }
}

Python实现

方法一：边界控制法

class SpiralMatrix:
    def spiral_order(self, matrix):
        """
        螺旋遍历矩阵 - 边界控制法
        时间复杂度：O(m*n)
        空间复杂度：O(1) 不计算结果数组
        """
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        result = []
        
        # 定义四个边界
        top, bottom = 0, m - 1
        left, right = 0, n - 1
        
        while top <= bottom and left <= right:
            # 1. 从左到右遍历上边界
            for j in range(left, right + 1):
                result.append(matrix[top][j])
            top += 1
            
            # 2. 从上到下遍历右边界
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1
            
            # 3. 从右到左遍历下边界（如果还有行）
            if top <= bottom:
                for j in range(right, left - 1, -1):
                    result.append(matrix[bottom][j])
                bottom -= 1
            
            # 4. 从下到上遍历左边界（如果还有列）
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1
        
        return result

方法二：方向数组法

class SpiralMatrixDirection:
    def spiral_order(self, matrix):
        """
        螺旋遍历矩阵 - 方向数组法
        时间复杂度：O(m*n)
        空间复杂度：O(m*n) 需要visited数组
        """
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        visited = [[False] * n for _ in range(m)]
        result = []
        
        # 方向数组：右、下、左、上
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        direction_idx = 0
        
        row, col = 0, 0
        
        for _ in range(m * n):
            result.append(matrix[row][col])
            visited[row][col] = True
            
            # 计算下一个位置
            next_row = row + directions[direction_idx][0]
            next_col = col + directions[direction_idx][1]
            
            # 检查是否需要转向
            if (next_row < 0 or next_row >= m or 
                next_col < 0 or next_col >= n or 
                visited[next_row][next_col]):
                direction_idx = (direction_idx + 1) % 4
                next_row = row + directions[direction_idx][0]
                next_col = col + directions[direction_idx][1]
            
            row, col = next_row, next_col
        
        return result

测试代码

public class SpiralMatrixTest {
    public static void main(String[] args) {
        SpiralMatrix solution = new SpiralMatrix();
        
        // 测试用例1：3x3矩阵
        int[][] matrix1 = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        System.out.println("3x3矩阵: " + solution.spiralOrder(matrix1));
        // 期望输出: [1, 2, 3, 6, 9, 8, 7, 4, 5]
        
        // 测试用例2：3x4矩阵
        int[][] matrix2 = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12}
        };
        System.out.println("3x4矩阵: " + solution.spiralOrder(matrix2));
        // 期望输出: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
        
        // 测试用例3：单行矩阵
        int[][] matrix3 = {{1, 2, 3, 4}};
        System.out.println("单行矩阵: " + solution.spiralOrder(matrix3));
        // 期望输出: [1, 2, 3, 4]
        
        // 测试用例4：单列矩阵
        int[][] matrix4 = {{1}, {2}, {3}};
        System.out.println("单列矩阵: " + solution.spiralOrder(matrix4));
        // 期望输出: [1, 2, 3]
    }
}

📊 复杂度分析

时间复杂度

• 所有方法：O(m × n)
  • 需要访问矩阵中的每个元素恰好一次
  • m 是矩阵的行数，n 是矩阵的列数

空间复杂度

• 边界控制法：O(1)

  • 只使用常数个额外变量
  • 不计算存储结果的数组

• 方向数组法：O(m × n)

  • 需要 visited 数组标记已访问元素
  • 额外空间与矩阵大小成正比

⚡ 算法优化

1. 空间优化

对于只需要遍历而不需要保存结果的场景，可以使用边界控制法避免额外空间：

public void spiralTraversal(int[][] matrix) {
    // 只遍历，不保存结果
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        // 遍历逻辑...
        for (int j = left; j <= right; j++) {
            process(matrix[top][j]); // 处理元素
        }
        top++;
        // ... 其他方向的遍历
    }
}

2. 代码简化

使用更简洁的边界判断：

def spiral_order_optimized(self, matrix):
    result = []
    while matrix:
        # 取第一行
        result.extend(matrix.pop(0))
        
        # 取每行的最后一个元素
        if matrix and matrix[0]:
            for row in matrix:
                result.append(row.pop())
        
        # 取最后一行（逆序）
        if matrix:
            result.extend(matrix.pop()[::-1])
        
        # 取每行的第一个元素（逆序）
        if matrix and matrix[0]:
            for row in reversed(matrix):
                result.append(row.pop(0))
    
    return result

🔄 变种问题

1. 螺旋矩阵 II（LeetCode 59）

问题： 给定正整数 n，生成一个包含 1 到 n² 所有元素的 n × n 正方形矩阵，要求按螺旋顺序填充。

public int[][] generateMatrix(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 j = left; j <= right; j++) {
            matrix[top][j] = num++;
        }
        top++;
        
        // 填充右边界
        for (int i = top; i <= bottom; i++) {
            matrix[i][right] = num++;
        }
        right--;
        
        // 填充下边界
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                matrix[bottom][j] = num++;
            }
            bottom--;
        }
        
        // 填充左边界
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
    }
    
    return matrix;
}

2. 螺旋矩阵 III（LeetCode 885）

问题： 在 R × C 的网格上，从 (r0, c0) 开始朝东走，按螺旋形状行走，返回网格顺序访问的坐标列表。

public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
    int[][] result = new int[R * C][2];
    int idx = 0;
    
    // 方向：东、南、西、北
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int d = 0; // 当前方向
    
    int r = r0, c = c0;
    result[idx++] = new int[]{r, c};
    
    if (R * C == 1) return result;
    
    for (int k = 1; k < 2 * (R + C); k += 2) {
        for (int i = 0; i < 2; i++) { // 每个k值走两个方向
            int steps = k + i; // 步数
            for (int j = 0; j < steps; j++) {
                r += dirs[d][0];
                c += dirs[d][1];
                if (0 <= r && r < R && 0 <= c && c < C) {
                    result[idx++] = new int[]{r, c};
                    if (idx == R * C) return result;
                }
            }
            d = (d + 1) % 4; // 转向
        }
    }
    
    return result;
}

3. 逆时针螺旋遍历

public List<Integer> spiralOrderCounterClockwise(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 = top; i <= bottom; i++) {
            result.add(matrix[i][left]);
        }
        left++;
        
        for (int j = left; j <= right; j++) {
            result.add(matrix[bottom][j]);
        }
        bottom--;
        
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result.add(matrix[i][right]);
            }
            right--;
        }
        
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                result.add(matrix[top][j]);
            }
            top++;
        }
    }
    
    return result;
}

🌟 实际应用

1. 图像处理

// 螺旋模糊效果
public void spiralBlur(int[][] image) {
    List<int[]> positions = getSpiralPositions(image);
    
    for (int i = 0; i < positions.size(); i++) {
        int[] pos = positions.get(i);
        int blurRadius = i / 10; // 螺旋程度决定模糊半径
        applyBlur(image, pos[0], pos[1], blurRadius);
    }
}

2. 游戏开发

// 地图螺旋生成
public void generateSpiralMap(int[][] map, int centerX, int centerY) {
    int value = 1;
    int size = map.length;
    
    // 从中心开始螺旋生成
    for (int layer = 0; layer < size / 2; layer++) {
        // 生成当前层的螺旋路径
        value = fillSpiralLayer(map, centerX, centerY, layer, value);
    }
}

3. 数据可视化

// 螺旋热力图
public void createSpiralHeatmap(double[][] data) {
    List<Integer> spiralOrder = getSpiralTraversalOrder(data);
    
    for (int i = 0; i < spiralOrder.size(); i++) {
        int pos = spiralOrder.get(i);
        int row = pos / data[0].length;
        int col = pos % data[0].length;
        
        // 根据螺旋位置设置颜色强度
        setHeatmapColor(row, col, data[row][col], i);
    }
}

📝 常见面试题

LeetCode 相关题目

1. LeetCode 54 - 螺旋矩阵

   • 难度：中等
   • 考点：边界控制、方向转换

2. LeetCode 59 - 螺旋矩阵 II

   • 难度：中等
   • 考点：矩阵填充、螺旋生成

3. LeetCode 885 - 螺旋矩阵 III

   • 难度：中等
   • 考点：坐标计算、边界判断

面试技巧

1. 画图理解

   • 在纸上画出矩阵和螺旋路径
   • 标记边界变化过程

2. 边界处理

   • 特别注意单行、单列矩阵
   • 确保循环终止条件正确

3. 代码简洁性

   • 选择最适合的方法
   • 避免冗余的边界检查

常见错误

1. 边界条件错误

   // 错误：没有检查是否还有行/列
   for (int j = right; j >= left; j--) {
       result.add(matrix[bottom][j]);
   }
   
   // 正确：添加边界检查
   if (top <= bottom) {
       for (int j = right; j >= left; j--) {
           result.add(matrix[bottom][j]);
       }
   }
   

2. 重复访问元素

   // 错误：边界更新位置不当
   for (int j = left; j <= right; j++) {
       result.add(matrix[top][j]);
   }
   // 忘记更新top
   
   // 正确：及时更新边界
   for (int j = left; j <= right; j++) {
       result.add(matrix[top][j]);
   }
   top++; // 立即更新边界
   

🧪 性能测试

public class SpiralMatrixPerformanceTest {
    public static void main(String[] args) {
        int[][] largeMatrix = generateMatrix(1000, 1000);
        
        // 测试边界控制法
        long start1 = System.currentTimeMillis();
        List<Integer> result1 = new SpiralMatrix().spiralOrder(largeMatrix);
        long time1 = System.currentTimeMillis() - start1;
        
        // 测试方向数组法
        long start2 = System.currentTimeMillis();
        List<Integer> result2 = new SpiralMatrixDirection().spiralOrder(largeMatrix);
        long time2 = System.currentTimeMillis() - start2;
        
        System.out.println("边界控制法耗时: " + time1 + "ms");
        System.out.println("方向数组法耗时: " + time2 + "ms");
        System.out.println("结果一致性: " + result1.equals(result2));
    }
    
    private static int[][] generateMatrix(int m, int n) {
        int[][] matrix = new int[m][n];
        int num = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = num++;
            }
        }
        return matrix;
    }
}

📚 学习总结

核心要点

1. 边界控制是关键：正确维护和更新四个边界
2. 方向转换要准确：按照固定顺序改变遍历方向
3. 特殊情况要考虑：单行、单列、空矩阵等边界情况
4. 代码要简洁：选择合适的实现方法，避免冗余逻辑

解题模板

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) {
        // 四个方向的遍历逻辑
        // 1. 右移
        // 2. 下移
        // 3. 左移（检查边界）
        // 4. 上移（检查边界）
    }
    
    return result;
}

学习建议

1. 多练习变种题目：熟悉不同的螺旋遍历场景
2. 注重边界处理：这是最容易出错的地方
3. 理解算法本质：掌握螺旋遍历的核心思想
4. 代码实现要熟练：能够快速写出bug-free的代码

螺旋矩阵问题虽然看似简单，但要写出正确、高效的代码需要仔细考虑边界条件和逻辑细节。通过充分的练习和理解，可以很好地掌握这类问题的解决方法。