【題目】

給你一個(gè) m 行 n 列的矩陣 matrix ，請(qǐng)按照 順時(shí)針螺旋順序 ，返回矩陣中的所有元素。

示例 1：

image.png

輸入： matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出： [1,2,3,6,9,8,7,4,5]

示例 2：

image.png

輸入： matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
輸出： [1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

【題目解析】

解題方法

解決螺旋矩陣問(wèn)題的關(guān)鍵是模擬遍歷過(guò)程，維護(hù)四個(gè)變量left、right、top、bottom來(lái)表示當(dāng)前遍歷的邊界，并按順序遍歷四個(gè)邊界上的元素。通過(guò)逐漸縮小邊界，我們可以模擬整個(gè)順時(shí)針遍歷的過(guò)程。

• 步驟一：從左到右遍歷上邊界的所有元素。
• 步驟二：從上到下遍歷右邊界的所有元素。
• 步驟三：如果適用，從右到左遍歷下邊界的所有元素。
• 步驟四：如果適用，從下到上遍歷左邊界的所有元素。
• 循環(huán)條件：每次遍歷完成后，相應(yīng)地縮小邊界，直到邊界不再重疊。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []
        
        rows, cols = len(matrix), len(matrix[0])
        left, right, top, bottom = 0, cols - 1, 0, rows - 1
        result = []
        
        while left <= right and top <= bottom:
            # 從左到右遍歷上層邊界
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            # 從上到下遍歷右側(cè)邊界
            for row in range(top + 1, bottom + 1):
                result.append(matrix[row][right])
            if left < right and top < bottom:
                # 從右到左遍歷下層邊界
                for col in range(right - 1, left, -1):
                    result.append(matrix[bottom][col])
                # 從下到上遍歷左側(cè)邊界
                for row in range(bottom, top, -1):
                    result.append(matrix[row][left])
            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
        
        return result

執(zhí)行效率

image.png

【總結(jié)】

適用問(wèn)題類型

螺旋矩陣問(wèn)題屬于數(shù)組遍歷與矩陣操作的范疇，特別是在需要按照特定順序訪問(wèn)矩陣元素的場(chǎng)合。此類問(wèn)題廣泛出現(xiàn)在圖像處理、數(shù)據(jù)轉(zhuǎn)換、以及任何涉及二維數(shù)據(jù)結(jié)構(gòu)操作的領(lǐng)域中。

解決算法

• 算法描述：模擬遍歷法通過(guò)模擬順時(shí)針螺旋的路徑來(lái)遍歷矩陣中的所有元素。算法核心在于動(dòng)態(tài)調(diào)整遍歷的邊界，即上下左右四個(gè)方向的界限，從而實(shí)現(xiàn)整個(gè)矩陣的順序遍歷。

• 算法特點(diǎn)：

  • 直觀性：該算法的邏輯簡(jiǎn)單直觀，易于理解和實(shí)現(xiàn)。
  • 靈活性：通過(guò)調(diào)整遍歷的方向和邊界條件，該方法可以應(yīng)用于不同形狀和大小的矩陣。
  • 無(wú)需額外空間：除了輸出結(jié)果所需的空間外，算法本身不需要額外的數(shù)據(jù)結(jié)構(gòu)。

時(shí)間復(fù)雜度與空間復(fù)雜度

• 時(shí)間復(fù)雜度：O(m*n)，其中m和n分別代表矩陣的行數(shù)和列數(shù)。算法需要遍歷矩陣中的每個(gè)元素一次。
• 空間復(fù)雜度：O(1)，算法在遍歷過(guò)程中僅需維護(hù)幾個(gè)變量來(lái)記錄邊界和方向，因此空間復(fù)雜度為常數(shù)級(jí)別。

實(shí)踐意義

• 廣泛應(yīng)用：模擬遍歷法不僅適用于螺旋矩陣問(wèn)題，還可以靈活應(yīng)用于其他需要特定順序訪問(wèn)數(shù)據(jù)的場(chǎng)景，如旋轉(zhuǎn)圖像、填充螺旋矩陣等。
• 算法教學(xué)：該問(wèn)題及其解法是教授數(shù)組和矩陣操作、掌握循環(huán)和邊界控制技巧的良好案例。
• 編程技巧：掌握這種模擬遍歷的方法有助于提升解決實(shí)際問(wèn)題的能力，尤其是在處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)時(shí)。

通過(guò)對(duì)螺旋矩陣問(wèn)題的深入分析，我們不僅能夠?qū)W習(xí)到如何有效地處理矩陣和數(shù)組中的數(shù)據(jù)，還能夠理解到算法設(shè)計(jì)中的邊界控制和循環(huán)遍歷技巧，為解決更復(fù)雜的算法問(wèn)題打下堅(jiān)實(shí)的基礎(chǔ)。

題目鏈接

螺旋矩陣