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;}
}
復雜度分析
- 時間復雜度：O(m * n)
- 每個元素遍歷一次。
- 空間復雜度：O(m * n)
- 使用了
visited二維數組記錄訪問情況。
- 使用了
適用場景
- 如果面試官要求實現更靈活的模擬法，則此解法是合適的替代。
- 不過，由于需要額外的
visited數組，其空間復雜度較高，不是首選。
快速AC總結
推薦解決方案
- 優先使用：邊界法（解法 1）
- 模擬螺旋順序，根據邊界進行縮小調整；
- 代碼簡潔高效，容易直接實現，完全滿足面試需求。
- 備選模擬法（解法 2）
- 如果需要通過靈活控制方向和遍歷行為進行實現，此解法較為通用，但需要額外空間。
在面試中如何快速AC
- 清晰描述解法：
- 解釋如何依次遍歷每一圈，使用上下左右邊界標記矩陣；
- 讓面試官了解整個遍歷順序和邊界調整的邏輯。
- 快速實現代碼：
- 邊界法（解法 1） 適合作為首選；
- 模擬移動的代碼少且簡潔，更容易寫。
- 關注邊界條件：
- 注意矩陣為空的情況；
- 單行單列、非方陣等特殊情況要覆蓋。
通過掌握這兩種解法，能夠靈活應對問題，并快速在面試中實現清晰的解答，獲得面試官肯定！
