0054. Spiral Matrix =================== 题目信息 -------- :题号: 0054. 螺旋矩阵 :难度: Medium :主题: 矩阵、模拟、边界收缩 :原题: `LeetCode 0054 `_ :重点: 从逐格记录访问状态,推导到用四条边界表示全部未输出位置 题目重述 -------- 给定一个 ``m × n`` 整数矩阵 ``matrix``,从左上角开始,按照向右、向下、向左、向上的顺时针螺旋顺序, 返回矩阵中的全部元素。 每个位置必须恰好输出一次。矩阵不一定是方阵。 约束为 ``1 <= m, n <= 10``、``-100 <= matrix[row][column] <= 100``。 自建示例 -------- .. code-block:: text 输入: [[ 1, 2, 3], [ 4, 5, 6], [ 7, 8, 9], [10,11,12]] 输出:[1,2,3,6,9,12,11,10,7,4,5,8] 输出外圈后,剩余区域是单列 ``[[5],[8]]``,继续从上向下输出。 .. code-block:: text 输入:[[4,5,6,7]] 输出:[4,5,6,7] 只有一行时,向右输出后矩形已经为空,不能再反向输出下边。 .. code-block:: text 输入:[[2],[3],[4]] 输出:[2,3,4] 只有一列时,首元素属于上边,其余元素属于右边;之后不能再向上重复输出左边。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: std::vector simulateWithVisited( const std::vector>& matrix ) { const int rows = static_cast(matrix.size()); const int columns = static_cast(matrix[0].size()); const int total = rows * columns; const int rowStep[4] = {0, 1, 0, -1}; const int columnStep[4] = {1, 0, -1, 0}; std::vector> visited( rows, std::vector(columns, false) ); std::vector result; result.reserve(total); int row = 0; int column = 0; int direction = 0; for (int count = 0; count < total; ++count) { result.push_back(matrix[row][column]); visited[row][column] = true; if (count + 1 == total) { break; } int nextRow = row + rowStep[direction]; int nextColumn = column + columnStep[direction]; const bool blocked = nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]; if (blocked) { direction = (direction + 1) % 4; nextRow = row + rowStep[direction]; nextColumn = column + columnStep[direction]; } row = nextRow; column = nextColumn; } return result; } std::vector shrinkBoundaries( const std::vector>& matrix ) { int top = 0; int bottom = static_cast(matrix.size()) - 1; int left = 0; int right = static_cast(matrix[0].size()) - 1; std::vector result; result.reserve(matrix.size() * matrix[0].size()); while (top <= bottom && left <= right) { for (int column = left; column <= right; ++column) { result.push_back(matrix[top][column]); } ++top; if (top > bottom) { break; } for (int row = top; row <= bottom; ++row) { result.push_back(matrix[row][right]); } --right; if (left > right) { break; } for (int column = right; column >= left; --column) { result.push_back(matrix[bottom][column]); } --bottom; if (top > bottom) { break; } for (int row = bottom; row >= top; --row) { result.push_back(matrix[row][left]); } ++left; } return result; } public: std::vector spiralOrder(std::vector>& matrix) { return shrinkBoundaries(matrix); } }; 题解 ---- 方向模拟基线 ~~~~~~~~~~~~ 最直接的方法保存当前位置、当前方向和访问表。方向按右、下、左、上的顺序循环;每输出一个位置,就尝试沿当前方向 前进一步。下一格越界或已经访问时,顺时针转向一次。 矩阵边界本身不足以判断是否转向。走完外圈后,下一格可能仍在矩阵范围内,却已经属于输出过的外圈。因此 ``simulateWithVisited`` 使用 ``m × n`` 访问表区分已输出位置和内部未输出位置。 循环固定执行 ``m × n`` 次。最后一个元素输出后直接结束,不再计算下一坐标,保证每次写入结果的坐标都真实有效。 这个方法完整模拟运动过程,时间为 ``O(mn)``,额外空间为 ``O(mn)``。 未访问矩形 ~~~~~~~~~~ 访问表记录了逐格状态,但螺旋遍历产生的未访问区域始终具有更强的结构:它是一个矩形。用四条边界表示该矩形: .. code-block:: text 行范围:[top, bottom] 列范围:[left, right] 每轮开始时保持以下不变量: * 边界围成的闭矩形恰好包含全部尚未输出的位置; * 矩形外的位置已经按螺旋顺序输出; * 已输出位置不会再次进入后续边界。 因此一轮只需依次输出当前矩形的上边、右边、下边和左边,再把四条边界向内收缩。剩余区域仍是矩形,下一轮可复用 相同过程。 边界收缩不变量 ~~~~~~~~~~~~~~ 上边一定存在,因此先输出 ``matrix[top][left..right]``,随后执行 ``top++``。右边从新的 ``top`` 开始,避免重复 右上角;下边从新的 ``right`` 开始,避免重复右下角;左边使用新的 ``bottom`` 和 ``top``,避免重复左侧角点。 每删除一条边后,都必须立即检查剩余矩形是否仍非空: .. code-block:: text 输出上边,top++ ;若 top > bottom,结束 输出右边,right-- ;若 left > right,结束 输出下边,bottom-- ;若 top > bottom,结束 输出左边,left++ 这些检查统一处理退化矩形。只有一行时,上边输出全部剩余元素,``top > bottom`` 后结束;只有一列时,上边输出顶部, 右边输出其余元素,``left > right`` 后结束。这样不会把同一行或同一列反向输出第二次。 每条边输出后立即离开未访问矩形,所以任何位置至多输出一次。只要矩形非空,上边就至少包含一个位置,算法会继续缩小 未访问区域;当行区间或列区间为空时,全部位置都已输出。因此每个位置恰好出现一次,输出顺序也与顺时针外层剥离 一致。 状态演化 ~~~~~~~~ 对 ``4 × 3`` 示例,第一轮边界变化如下: .. list-table:: :header-rows: 1 * - 阶段 - 输出 - 剩余矩形 * - 上边 - ``1,2,3`` - 行 ``[1,3]``,列 ``[0,2]`` * - 右边 - ``6,9,12`` - 行 ``[1,3]``,列 ``[0,1]`` * - 下边 - ``11,10`` - 行 ``[1,2]``,列 ``[0,1]`` * - 左边 - ``7,4`` - 行 ``[1,2]``,列 ``[1,1]`` 第二轮只剩一列。上边输出 ``5``,右边输出 ``8``;随后列区间为空,遍历结束。 代码演进 ~~~~~~~~ ``simulateWithVisited`` 逐格模拟方向变化,访问表直接阻止重复进入已输出位置,适合作为定义对应的基线。 ``shrinkBoundaries`` 利用未访问区域始终为矩形的结构,把 ``mn`` 个访问标记压缩成四条边界。公开入口采用该方法, 因为它保持相同的线性时间,并把额外空间降为常量。 复杂度分析 ~~~~~~~~~~ 矩阵共有 ``mn`` 个位置,两种方法都恰好输出每个位置一次,时间复杂度为 ``O(mn)``。 方向模拟使用 ``O(mn)`` 的访问表。边界收缩除返回数组外只维护四条边界和循环变量,额外空间为 ``O(1)``。