左神算法之螺旋打印

螺旋方式打印矩阵

1. 题目

用螺旋的方式打印矩阵，比如下面的矩阵：

0 1 2 3
4 5 6 7 
8 9 10 11

打印顺序为：0 1 2 3 7 11 10 9 8 4 5 6

2. 解释

螺旋打印矩阵是指从外向内顺时针方向依次打印矩阵的每一层元素。具体来说：

1. 从左上角(0,0)开始，向右打印第一行的所有元素
2. 向下打印最右列的元素（除去第一行已打印的元素）
3. 向左打印最底行的元素（除去最右列已打印的元素）
4. 向上打印最左列的元素（除去最底行和第一行已打印的元素）
5. 重复这个过程，向内层螺旋，直到所有元素都被打印

对于示例矩阵，打印顺序如下：

• 向右：0→1→2→3
• 向下：7→11
• 向左：10→9→8
• 向上：4
• 向右：5→6

3. 思路

我们可以使用四个边界变量来定义当前螺旋层的范围：

1. 定义四个边界：上边界(top)、下边界(bottom)、左边界(left)、右边界(right)
2. 按照顺时针方向依次打印：
   • 从左到右打印上边界行
   • 从上到下打印右边界列
   • 从右到左打印下边界行（如果上边界不等于下边界）
   • 从下到上打印左边界列（如果左边界不等于右边界）
3. 每完成一圈螺旋，缩小边界范围（top++, bottom–, left++, right–）
4. 重复上述过程直到所有元素都被打印

进行一圈圈的缩小，输出这两个点的边框的值

缩小到最后有三种情况：按照这个三种情况进行分情况输出

4. 代码

public class Problem04_PrintMatrixSpiralOrder {

    public static void printMatrixSpiralOrder(int[][] matrix) {
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while(tR <= dR && tC <= dC) {
            printLevel(matrix, tR++, tC++, dR--, dC--);
        }
    }

    // [a, b]是左上角，[c, d]是右下角
    public static void printLevel(int[][] matrix, int a, int b, int c, int d) {
        if( a == c ){
            for(int i = b; i <= d; i++){
                System.out.print(matrix[a][i] + " ");
            }
        }else if( b == d ){
            for(int i = a; i <= c; i++){
                System.out.print(matrix[i][b] + " ");
            }
        }else{
            int curC = b;
            int curR = a;
            while(curC != d){
                System.out.print(matrix[a][curC] + " ");
                curC ++;
            }
            while(curR != c){
                System.out.print(matrix[curR][d] + " ");
                curR ++;
            }
            while(curC != b){
                System.out.print(matrix[c][curC] + " ");
                curC --;
            }
            while(curR != a){
                System.out.print(matrix[curR][b] + " ");
                curR --;
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };
        printMatrixSpiralOrder(matrix);
    }
}

5. 总结

螺旋打印矩阵的关键在于：

1. 使用四个边界变量(top, bottom, left, right)来定义当前螺旋层
2. 按照顺时针方向依次打印四条边
3. 每次完成一圈后缩小边界范围
4. 处理特殊情况（单行或单列情况）

这种方法的时间复杂度是O(M×N)，其中M和N分别是矩阵的行数和列数，因为我们只访问每个元素一次。空间复杂度是O(1)，只使用了常数个额外变量。

螺旋遍历在图像处理、矩阵运算、二维数组操作等场景中有广泛应用。掌握这种遍历方式有助于解决许多与矩阵相关的问题。