Leetcode 分類刷題 —— 隊列（Queue）

1、題目描述：

Leetcode 54. Spiral Matrix 螺旋矩陣

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

2、解題思路：

迭代版：按層模擬，將矩陣看成若干層，首先輸出最外層的元素，其次輸出次外層的元素，直到輸出最內(nèi)層的元素。

3、代碼（迭代版）

import java.util.*;

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

        // 處理特殊情況，矩陣為空或行列數(shù)為0
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return result;
        }

        // 定義矩陣的行數(shù)和列數(shù)
        int rows = matrix.length, columns = matrix[0].length;

        // 定義四個指針，分別代表矩陣的上下左右四個邊界
        int top = 0, bottom = rows - 1, left = 0, right = columns - 1;

        // 當四個指針沒有相遇時，持續(xù)循環(huán)
        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);
    }
}

該解決方案使用遞歸函數(shù)spiralOrderHelper來處理每個子矩陣。
函數(shù)接受四個參數(shù)：上邊界top，下邊界bottom，左邊界left和右邊界right。
該函數(shù)首先檢查邊界是否有效，然后按照螺旋順序?qū)⒆泳仃囍械脑靥砑拥浇Y(jié)果列表中。如果子矩陣的寬度和高度均大于1，則遞歸處理該子矩陣的內(nèi)部。
注意，遞歸函數(shù)中的邊界是收縮的，因此需要在遞歸函數(shù)之外初始化邊界。

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