使用递归解决螺旋矩阵问题

面试时被要求写一段代码，螺旋输出一个二维数组。比如，对于下面这个二维数组，要求按图示的方向进行元素的输出：

由于平时专注写业务，很少关注算法，这个问题一下把我整蒙了(shy...)，思维打不开，到最后也没回答上来。

昨晚睡觉前又思考了一翻这个问题，想到削苹果的场景，如果在削苹果时，按同一个方向一层一层的往里削，等把苹果连皮带核削完时(残忍吧)，整个(苹果)矩阵也就遍历结束了。

于是我想，在螺旋遍历过程中，把遍历的元素都给移除掉(相当于削皮)，第一层移除完后，再递归移除剩下的，直到没有可移除的，问题不就解决了吗？

接着想，怎么削第一层皮？

观察上图，对于二维数组来说，第一层皮显然是由 数组的第一行、最后一列、最后一行、第一列组成的（注意这个顺时针的顺序）。我们用变量 step
代表这个顺序，其是 number
类型，取值 0
到 3
，当 step
等于：

• 0
  : 表示要从左到右输出矩阵的第一行；
• 1
  : 表示要从上到下输出矩阵的最后一列；
• 2
  : 表示要从右到左输出矩阵的最后一行；
• 3
  : 表示要从下往上输出矩阵的第一列；

再次强调，输出的过程也是从矩阵中移除这些元素的过程。当 step = 3
的逻辑执行完后，我们再递归从 0
开始。

所以整个螺旋输出矩阵元素的代码如下：

function spiralOrder(matrix) {    // 方法返回值    const res = [];    // 往返回值中追加数据    const append = (v) => res.push(v);    // 递归遍历    traverse(matrix);    // 返回螺旋收集的值    return res;    /**     * 递归螺旋遍历矩阵     *     * @param arr 待遍历的矩阵数据     * @param step 走到第几步了     */    function traverse(arr, step = 0) {        if (!arr?.length) {            return;        }        // 遍历首行        if (step === 0) {            const [first] = arr;            if (!first?.length) {                // 遍历完了                return;            }            first.forEach(append);            traverse(arr.slice(1), step + 1);            return;        }        // 遍历最后一列        if (step === 1) {            arr.forEach((v) => append(v.pop()));            traverse(arr, step + 1);            return;        }        // 遍历最后一行        if (step === 2) {            const last = arr.pop();            if (!last?.length) {                // 遍历完了                return;            }            last.reverse().forEach(append);            traverse(arr, step + 1);            return;        }        // 遍历第一列        if (step === 3) {            arr.forEach((v, i, a) => {                const row = a.length - i - 1;                append(a[row].shift());            });            // 回到开始            traverse(arr);        }    }}
复制

测试看看：

const h = [    [1, 2, 3],    [8, 9, 4],    [7, 6, 5],];const i = [    [1,  2,  3],    [10, 11, 4],    [9,  12, 5],    [8,  7,  6],];[h, i].forEach((v) => {    console.log('#'.repeat(10));    console.log(v);    const res = spiralOrder(v);    console.log(res);});

复制

运行结果如下：

注意，

1. 我这里只是提供了一个可行的解决方式，但并非是最优的。
2. 如果你不想改变入参，可以将矩阵数据先拷贝一份再执行。