59. Spiral Matrix II
MediumDescription
給定一個正整數
n，生成一個 n x n 的矩陣，按照螺旋順序填入 1 到 n^2。
Example:
Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]
Intuition#
核心思路：模擬螺旋行走——用四個邊界控制上下左右的移動範圍，每走完一邊就收縮邊界。
- 與 Spiral Matrix (54) 讀取螺旋相反，這題是寫入螺旋
- 用 top/bottom/left/right 四個邊界追蹤未填入的範圍
- 依序走：右 -> 下 -> 左 -> 上，每走完一邊收縮對應邊界
- 從 1 填到 n*n
Approaches#
⭐1: 四邊界模擬#
- 概念: 維護四個邊界，依序填入右、下、左、上方向的數字，每完成一邊就收縮邊界
- 時間複雜度:
O(n^2)- 填入 n^2 個數字 - 空間複雜度:
O(n^2)- 輸出矩陣（不算額外空間則 O(1)）
class Solution {
fun generateMatrix(n: Int): Array<IntArray> {
val matrix = Array(n) { IntArray(n) }
var top = 0
var bottom = n - 1
var left = 0
var right = n - 1
var num = 1
while (top <= bottom && left <= right) {
// 向右
for (col in left..right) {
matrix[top][col] = num++
}
top++
// 向下
for (row in top..bottom) {
matrix[row][right] = num++
}
right--
// 向左
for (col in right downTo left) {
matrix[bottom][col] = num++
}
bottom--
// 向上
for (row in bottom downTo top) {
matrix[row][left] = num++
}
left++
}
return matrix
}
}2: 方向陣列模擬#
- 概念: 用方向陣列定義四個方向，碰到邊界或已填元素時轉向
- 時間複雜度:
O(n^2) - 空間複雜度:
O(n^2)
class Solution {
fun generateMatrix(n: Int): Array<IntArray> {
val matrix = Array(n) { IntArray(n) }
val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(-1, 0))
var dir = 0
var row = 0
var col = 0
for (num in 1..n * n) {
matrix[row][col] = num
val nextRow = row + dirs[dir][0]
val nextCol = col + dirs[dir][1]
// 碰到邊界或已填格子就轉向
if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n || matrix[nextRow][nextCol] != 0) {
dir = (dir + 1) % 4
}
row += dirs[dir][0]
col += dirs[dir][1]
}
return matrix
}
}🔑 Takeaways#
- Pattern: 螺旋矩陣系列——四邊界收縮法是最直覺的模擬方式
- 關鍵技巧: 填入版本比讀取版本更簡單，因為不需要處理非正方形的邊界條件