螺旋矩阵 IV

难度: Medium

给你两个整数：m 和 n ，表示矩阵的维数。

另给你一个整数链表的头节点 head 。

请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按螺旋顺序填充。如果还存在剩余的空格，则用 -1 填充。

返回生成的矩阵。

示例 1：

输入：m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
输出：[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
解释：上图展示了链表中的整数在矩阵中是如何排布的。
注意，矩阵中剩下的空格用 -1 填充。

示例 2：

输入：m = 1, n = 4, head = [0,1,2]
输出：[[0,1,2,-1]]
解释：上图展示了链表中的整数在矩阵中是如何从左到右排布的。 
注意，矩阵中剩下的空格用 -1 填充。

提示：

1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
链表中节点数目在范围 [1, m * n] 内
0 <= Node.val <= 1000

Submission

运行时间: 260 ms

内存: 53.9 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        res = [[-1] * n for _ in range(m)]
        t, b, l, r = 0, m - 1, 0, n - 1
        current = head
        while current:
            for i in range(l, r + 1):
                if not current:
                    return res
                res[t][i] = current.val
                current = current.next
            t += 1
            # if t > b:
            #     break
            for j in range(t, b + 1):
                if not current:
                    return res
                res[j][r] = current.val
                current = current.next
            r -= 1
            # if r < l:
            #     break
            for i in range(r, l - 1, -1):
                if not current:
                    return res
                res[b][i] = current.val
                current = current.next
            b -= 1
            # if b < t:
            #     break
            for j in range(b, t - 1, -1):
                if not current:
                    return res
                res[j][l] = current.val
                current = current.next
            l += 1
            # if l > r:
            #     break
        return res

Explain

题解的思路是首先创建一个m x n的矩阵，初始化所有元素为-1。然后定义四个变量t, b, l, r分别表示矩阵的上边界、下边界、左边界和右边界。通过一个while循环，按螺旋顺序逐个填充矩阵。每填充完一圈（或矩阵的一部分），就相应地更新边界变量（例如填充完顶部一行后，t自增）。循环每次检查链表是否还有节点，如果没有，即提前返回矩阵。否则，继续填充直到链表耗尽。

时间复杂度: O(max(L, m * n))

空间复杂度: O(m * n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        res = [[-1] * n for _ in range(m)]  # 创建结果矩阵并初始化为-1
        t, b, l, r = 0, m - 1, 0, n - 1  # 初始化上下左右边界
        current = head  # 开始的链表节点
        while current:  # 只要链表还有节点
            for i in range(l, r + 1):  # 从左到右填充上边界
                if not current:  # 如果链表节点用完，直接返回结果
                    return res
                res[t][i] = current.val  # 赋值
                current = current.next  # 移动链表节点
            t += 1  # 向内移动上边界
            for j in range(t, b + 1):  # 从上到下填充右边界
                if not current:
                    return res
                res[j][r] = current.val
                current = current.next
            r -= 1  # 向内移动右边界
            for i in range(r, l - 1, -1):  # 从右到左填充下边界
                if not current:
                    return res
                res[b][i] = current.val
                current = current.next
            b -= 1  # 向内移动下边界
            for j in range(b, t - 1, -1):  # 从下到上填充左边界
                if not current:
                    return res
                res[j][l] = current.val
                current = current.next
            l += 1  # 向内移动左边界
        return res  # 返回最终结果矩阵

Explore

是的，这种更新机制能确保不会发生数组越界。在每次填充过程中，边界变量t（上边界）、b（下边界）、l（左边界）、r（右边界）的更新都是基于已经填充的范围进行的。例如，当从左至右填充完上边界后，t自增，这意味着上边界向下移动，因此任何后续对上边界的引用都不会越界。同样的逻辑适用于其他三个边界。每次填充操作后，相应的边界都会立即更新，限制未来操作的范围，从而避免了越界的可能性。

通过循环和边界更新的方式，代码确保了所有应该被填充的格子都被正确填充。每次填充操作只发生在当前边界定义的范围内，填充后即刻更新边界以缩小下一次操作的范围。这种方法确保每个方向的填充都不会重叠或漏填。向内移动的边界操作严格遵循螺旋顺序，逐层向内收缩，直到所有可能的格子都被访问和填充。这种结构化的填充过程和边界控制相结合，保证了矩阵的每个部分都被恰当处理。

在题解中，如果链表元素在矩阵填充过程中用尽，那么任何未被填充的部分将保持其初始值-1，这是在创建矩阵时预设的。这意味着函数在链表节点耗尽时能够立即返回当前的矩阵状态，其中包括已经填充的值和任何未被覆盖的-1值。这种处理方式确保了函数总是能返回一个完整的m x n矩阵，即使不是所有的格子都被链表中的元素填充。