面试题29：顺时针打印矩阵

从“每圈都一定有四条边吗”开始

先预测：矩阵只有一行1、2、3、4、5。若仍执行“上、右、下、左”四段，会发生什么？上边已经打印五个数，右边没有新行，下边却可能再从右向左打印一次。问题不在顺时针方向，而在把退化成线段的一圈误当成了矩形边框。

作者解决“顺时针打印矩阵”时，不维护会在圈内变化的上下左右四个变量，而是让第k圈的环起点固定为start。由它计算右端列endX与下端行endY，再按上、右、下、左依次处理。每完成一圈才增加start。

这就是原书的“按圈打印”：先把二维问题切成若干个边框，再把一个边框切成至多四段单向循环。退化层可能只有上边、上边加右边，或上右下三边；是否存在后续边必须由宽高分别判断。

环起点为何能同时代表行和列

第0圈左上角是(0,0)，第1圈是(1,1)，第2圈是(2,2)。每深入一圈，顶部删一行、底部删一行、左侧删一列、右侧删一列，所以左上角的两个坐标始终同步增加。

设矩阵有rows行、columns列。第start圈存在，当且仅当columns大于2×start并且rows大于2×start。换成原书概念，就是“起点行列小于行列的一半”；对奇数尺寸要理解为仍允许中心那一行、列或点，不能直接使用向下取整的一半把它排除。

进入一圈时的循环不变量是：start外侧的所有元素已经按顺时针顺序输出；start内侧尚未访问；当前剩余矩形的左上角恰为(start,start)。它的为：

• endX等于columns减1再减start；
• endY等于rows减1再减start。

外层条件先保证start没有越过矩阵，因而endX与endY都不小于start。内层再判断是否真的存在高度或宽度，避免重复访问。

四条边的条件为何逐步变严（边界条件）

第一条上边总存在，因为能进入当前圈就至少剩一个元素。它从列start走到endX，包含左上与右上两个角。第二条右边必须要求start小于endY，也就是至少两行；从start加1开始，故不重复右上角。

第三条下边需要至少两列且至少两行，即start小于endX并且start小于endY。它从endX减1反向走到start，跳过右下角而保留左下角。第四色边还要至少三行：start小于endX并且start小于endY减1；它从endY减1走到start加1，同时跳过左下与左上。

这些判断合起来就是“单行单列边界”的完整处理，而不是笼统地在每段后检查一次。可以把理解为“这条边是否还有独占元素”：

1. 单点只有上边的一个元素。 2.只有上边，不能执行下边。 3.先由上边取顶部，再由右边向下取其余元素，不能执行左边。
2. 两行矩阵执行上、右、下，左边没有独占元素。
3. 至少两列且三行以上，四条边才都可能有独占元素。

忠实还原作者的输出式实现

作者接口接收int二维指针、列数和行数，直接调用printNumber输出，不构造返回容器。外层先拒绝空指针、非正列数和非正行数；然后逐圈调用PrintMatrixInCircle。

#include <cstdio>
 
void printNumber(int number) {
    std::printf("%d\t", number);
}
 
void PrintMatrixInCircle(int** numbers,
                         int columns,
                         int rows,
                         int start) {
    const int endX = columns - 1 - start;
    const int endY = rows - 1 - start;
 
    for (int i = start; i <= endX; ++i) {
        printNumber(numbers[start][i]);
    }
 
    if (start < endY) {
        for (int i = start + 1; i <= endY; ++i) {
            printNumber(numbers[i][endX]);
        }
    }
 
    if (start < endX && start < endY) {
        for (int i = endX - 1; i >= start; --i) {
            printNumber(numbers[endY][i]);
        }
    }
 
    if (start < endX && start < endY - 1) {
        for (int i = endY - 1; i >= start + 1; --i) {
            printNumber(numbers[i][start]);
        }
    }
}
 
void PrintMatrixClockwisely(int** numbers,
                            int columns,
                            int rows) {
    if (numbers == nullptr || columns <= 0 || rows <= 0) {
        return;
    }
 
    int start = 0;
    while (columns > start * 2 && rows > start * 2) {
        PrintMatrixInCircle(numbers, columns, rows, start);
        ++start;
    }
}

四段循环的端点也是去重证明：上边拥有两个顶角；右边从下一行开始；下边从左一列开始；左边同时排除上下角。角点没有依赖额外集合去判重，而是在循环区间中被静态分配给最先经过它的边。

输出式接口的优点是额外空间O(1)，适合原题“打印”语义；缺点是算法和I/O耦合，不方便断言完整结果、复用为网络响应或中途取消。把printNumber改成回调可以保留流式特征，也可以返回vector以提高可测性。

返回序列版本与矩形输入契约

现代C++常用vector嵌套表达矩阵。先检查外层为空、首行为空，再检查所有行长度一致；否则所谓columns没有全局含义。下面仍沿用作者的start模型，但把每个访问值加入结果。

#include <cstddef>
#include <stdexcept>
#include <vector>
 
std::vector<int> spiralOrder(
    const std::vector<std::vector<int>>& matrix) {
    if (matrix.empty() || matrix.front().empty()) {
        return {};
    }
 
    const std::size_t rows = matrix.size();
    const std::size_t columns = matrix.front().size();
    for (const auto& row : matrix) {
        if (row.size() != columns) {
            throw std::invalid_argument("matrix must be rectangular");
        }
    }
 
    std::vector<int> result;
    result.reserve(rows * columns);
 
    for (std::size_t start = 0;
         start < columns - start && start < rows - start;
         ++start) {
        const std::size_t endX = columns - 1 - start;
        const std::size_t endY = rows - 1 - start;
 
        for (std::size_t col = start; col <= endX; ++col) {
            result.push_back(matrix[start][col]);
        }
        if (start < endY) {
            for (std::size_t row = start + 1; row <= endY; ++row) {
                result.push_back(matrix[row][endX]);
            }
        }
        if (start < endX && start < endY) {
            for (std::size_t col = endX; col-- > start;) {
                result.push_back(matrix[endY][col]);
            }
        }
        if (start < endX && start + 1 < endY) {
            for (std::size_t row = endY; --row > start;) {
                result.push_back(matrix[row][start]);
            }
        }
    }
    return result;
}

无符号索引不能照抄i大于等于start后递减的写法：当start为0时，i从0再减会绕到极大值。倒序循环采用后减判断，让循环体拿到endX减1直到start；左边则先减再比较。外层也避免start乘2可能发生的溢出，改用start小于dimension减start，并且减法发生前已知start小于dimension。

返回序列需要O(rows×columns)输出空间；若不计题目要求的输出，控制变量仍是O(1)。每个元素恰好访问一次，因此时间O(rows×columns)。环数约为min(rows,columns)的一半，但每圈周长之和仍是元素总数。

与四边界收缩法的关系

旧页使用top、bottom、left、right，每走完一边就收缩一次。这是等价变体，但作者源码的阅读重点是“圈起点固定、四段条件独立”。四边界法在一圈中途改变状态，必须在下边和左边前重新判断；start法在一圈内端点不变，用几何条件直接决定边是否存在。

两者都能做到每个元素一次、常量控制空间。面试中若题目要求解释书中代码，应先复现start不变量与四个条件；若工程团队已有统一矩阵遍历框架，可以使用四边界法，但测试仍要覆盖相同退化层。

由返回序列反推矩阵并不唯一，因为rows与columns未知时，不同形状可能产生同一串值。若输入同时给定形状，才可按相同四段路径把序列填回网格。顺时针读取与螺旋填充共享路径生成器，可抽成访问坐标的迭代器，但只有在多个业务确实复用时才值得增加抽象。

作者十二组测试怎样覆盖形状

源码不是随机挑几块方阵，而是系统测试十二种尺寸：1×1、2×2、4×4、5×5；1×5、2×5、3×5、4×5；以及5×1、5×2、5×3、5×4。前四组覆盖最小、偶数方阵、奇数中心点；中四组让行多于列；后四组让列多于行。

这里的尺寸参数顺序是Test(columns, rows)，不能误读为常见的rows在前。例如Test(1,5)是五行一列，按1、2、3、4、5向下打印；Test(5,1)是一行五列，按1到5向右打印。两者输出恰好相同，但经历的边条件不同，因此必须同时保留。

作者Test函数按行填入连续整数。这样输出顺序能直接暴露坐标错误：5×5应先得到1到5，再得到10、15、20、25，然后24到21、16、11、6，接着进入start为1的内圈，最后中心13。若角点重复或残层漏掉，输出长度不再等于25。

自动测试不应只看元素数量，因为重复一个元素并漏掉另一个时长度仍正确；要断言完整序列，并额外验证输入没有被修改：

#include <cassert>
#include <vector>
 
void testSpiralOrder() {
    using Matrix = std::vector<std::vector<int>>;
 
    assert(spiralOrder({}) == std::vector<int>{});
    assert(spiralOrder({{1}}) == std::vector<int>{1});
    assert(spiralOrder({{1, 2, 3, 4, 5}}) ==
           (std::vector<int>{1, 2, 3, 4, 5}));
    assert(spiralOrder({{1}, {2}, {3}, {4}, {5}}) ==
           (std::vector<int>{1, 2, 3, 4, 5}));
 
    Matrix square{{1, 2, 3, 4},
                  {5, 6, 7, 8},
                  {9, 10, 11, 12},
                  {13, 14, 15, 16}};
    const Matrix snapshot = square;
    assert(spiralOrder(square) ==
           (std::vector<int>{1, 2, 3, 4, 8, 12, 16, 15,
                             14, 13, 9, 5, 6, 7, 11, 10}));
    assert(square == snapshot);
 
    bool rejected = false;
    try {
        (void)spiralOrder({{1, 2}, {3}});
    } catch (const std::invalid_argument&) {
        rejected = true;
    }
    assert(rejected);
}

生产测试还应逐一生成作者十二种尺寸，并以一个可信的坐标模型交叉校验。极大尺寸要先检查rows乘columns是否溢出再reserve；若输出到流，则测试写入内存接收器并核对顺序。对异常矩形输入，接口可以抛错、返回错误类型或在类型层面禁止，不能静默按首行宽度访问短行。

坐标级属性测试可以把每次访问的(row,col)记入与输入同尺寸的计数矩阵。结束后，访问次数总和必须等于rows乘columns，每个格子的计数必须恰为1，相邻输出坐标必须共享一条边；发生转向时方向只能按右、下、左、上的循环推进。前三条分别检验不漏、不重与路径连续，最后一条检验顺时针次序。它比只比较排序后的值更强，因为输入可能含重复数字，值集合无法说明究竟访问了哪个格子。

还可以让作者输出版与返回序列版对同一批随机矩形交叉校验：把printNumber替换为收集回调，两个结果应完全相同。这样既保住原书控制流，又能发现现代化改写中的无符号倒序错误。若回调在第k个元素返回失败，推荐立即停止并返回已处理数量或错误对象；继续走完整圈会让调用方误以为失败之后的副作用没有发生。

正确性证明

先证明单圈。上边覆盖(start,start)到(start,endX)；若存在右边，它覆盖(start+1,endX)到(endY,endX)；若存在下边，它覆盖(endY,endX-1)到(endY,start)；若存在左边，它覆盖(endY-1,start)到(start+1,start)。四个集合不相交，按连接次序组成当前边框全部未访问元素。

再对start归纳。第0圈前没有元素被访问。假设进入第start圈时外侧所有圈已按序完整输出、内侧均未访问；单圈结论保证当前边框恰好输出一次。start加1后，不变量对下一圈成立。循环停止时至少一个维度已无剩余坐标，因此全部元素已输出。

这个证明也解释为什么仅靠“看起来像螺旋”不够：必须同时证明覆盖性、不重复性、顺序性和终止性。边条件负责覆盖退化形状，错开的端点负责不重复，四段次序负责顺时针，start单调增加且受最短维度限制负责终止。

工程边界与变体

若矩阵元素是大对象，返回vector会复制；可以返回坐标序列、传入访问回调，或对可复制类型移动输出，但不能移动后又要求输入保持不变。只读遍历应接收const引用，作者的int双指针是历史接口，不表达行长度，也不拥有内存。

并发读取要求矩阵在遍历期间尺寸与元素稳定。另一个线程若缩短某行或释放底层内存，会使已计算的endX、endY失效；使用不可变快照或外部读锁。流式printNumber失败时，接口也要决定是停止并返回错误，还是继续；原示例省略了I/O错误传播。

逆时针版本可以按左、下、右、上的顺序重新分配角点，不能只把最终结果reverse：反转顺时针序列会从最后访问的内层元素开始，不再从左上角起步。若起点或方向可配置，应先明确“起点、首方向、转向”三个参数，再生成路径。

本章练习

本章回顾

1. 作者按圈打印，每圈左上角由同一个start表示。
2. 当前环右下角为endX与endY，外层条件保证环仍存在。
3. 上边总执行，右边要求至少两行，下边要求至少两行两列，左边还要求至少三行。
4. 四段循环通过错开端点静态分配角点，不需要集合判重。
5. 单行、单列、两行与两列残层决定第四色边是否存在。
6. 输出式接口控制空间O(1)，返回序列版便于测试但占用结果空间。
7. 无符号倒序要防止下溢，嵌套vector要验证所有行等长。
8. 作者十二组测试覆盖方阵、窄高、宽矮、奇偶尺寸和中心残层。

名词解释