Leetcode 分类刷题 —— 队列（Queue）

1、题目描述：

Leetcode 54. Spiral Matrix 螺旋矩阵

Given an m x n matrix, return all elements of the matrix in spiral order.

2、解题思路：

迭代版：按层模拟，将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。

3、代码（迭代版）

import java.util.*;

/**
 * @author ChatGPT
 * @date 2022/3/21
 */
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();

        // 处理特殊情况，矩阵为空或行列数为0
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return result;
        }

        // 定义矩阵的行数和列数
        int rows = matrix.length, columns = matrix[0].length;

        // 定义四个指针，分别代表矩阵的上下左右四个边界
        int top = 0, bottom = rows - 1, left = 0, right = columns - 1;

        // 当四个指针没有相遇时，持续循环
        while(top <= bottom && left <= right){
            // 遍历矩阵的第一行，从左到右
            for(int column = left; column <= right; column++){
                result.add(matrix[top][column]);
            }
            // 遍历矩阵的最后一列，从上到下，需要判断是否越界
            for(int row = top + 1; row <= bottom && left <= right; row++){
                result.add(matrix[row][right]);
            }
            // 遍历矩阵的最后一行，从右到左，需要判断是否越界
            for(int column = right - 1; column >= left && top < bottom; column--){
                result.add(matrix[bottom][column]);
            }
            // 遍历矩阵的第一列，从下到上，需要判断是否越界
            for(int row = bottom - 1; row > top && left < right; row--){
                result.add(matrix[row][left]);
            }
            // 更新指针，缩小矩阵范围
            top++;
            bottom--;
            left++;
            right--;
        }
        return result;
    }
}

3、代码（递归版）

/**
 * @author ChatGPT
 * @date 2022/3/21
 */
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;
        spiralOrderHelper(matrix, 0, m - 1, 0, n - 1, result);
        return result;
    }

    private void spiralOrderHelper(int[][] matrix, int top, int bottom, int left, int right, List<Integer> result) {
        if (left > right || top > bottom) {
            return;
        }
        for (int i = left; i <= right; i++) {
            result.add(matrix[top][i]);
        }
        for (int i = top + 1; i <= bottom; i++) {
            result.add(matrix[i][right]);
        }
        if (top < bottom && left < right) {
            for (int i = right - 1; i >= left; i--) {
                result.add(matrix[bottom][i]);
            }
            for (int i = bottom - 1; i > top; i--) {
                result.add(matrix[i][left]);
            }
        }
        spiralOrderHelper(matrix, top + 1, bottom - 1, left + 1, right - 1, result);
    }
}

该解决方案使用递归函数spiralOrderHelper来处理每个子矩阵。
函数接受四个参数：上边界top，下边界bottom，左边界left和右边界right。
该函数首先检查边界是否有效，然后按照螺旋顺序将子矩阵中的元素添加到结果列表中。如果子矩阵的宽度和高度均大于1，则递归处理该子矩阵的内部。
注意，递归函数中的边界是收缩的，因此需要在递归函数之外初始化边界。

参考文章：
https://leetcode.cn/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/