# Spiral Matrix

### 描述​

Given a matrix of m × n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]

You should return [1,2,3,6,9,8,7,4,5].

### 解法 1 迭代​

// Spiral Matrix// 时间复杂度O(n^2)，空间复杂度O(1)public class Solution {    public List<Integer> spiralOrder(int[][] matrix) {        List<Integer> result = new ArrayList<>();        if (matrix.length == 0) return result;        int beginX = 0, endX = matrix[0].length - 1;        int beginY = 0, endY = matrix.length - 1;        while (true) {            // From left to right            for (int j = beginX; j <= endX; ++j) result.add(matrix[beginY][j]);            if (++beginY > endY) break;            // From top to bottom            for (int i = beginY; i <= endY; ++i) result.add(matrix[i][endX]);            if (beginX > --endX) break;            // From right to left            for (int j = endX; j >= beginX; --j) result.add(matrix[endY][j]);            if (beginY > --endY) break;            // From bottom to top            for (int i = endY; i >= beginY; --i) result.add(matrix[i][beginX]);            if (++beginX > endX) break;        }        return result;    }}

### 解法 2 递归​

// Spiral Matrix// 时间复杂度O(n^2)，空间复杂度O(1)public class Solution {    public List<Integer> spiralOrder(int[][] matrix) {        List<Integer> result = new ArrayList<>();        if (matrix.length == 0) return result;        left = 0;        right = matrix[0].length - 1;        up = 0;        down = matrix.length - 1;        dfs(matrix, 0, 0, 0, result);        return result;    }    private void dfs(int[][] matrix, int i, int j, int direction,                     List<Integer> result) {        if (i < up || i > down) return;        if (j < left || j > right) return;        result.add(matrix[i][j]);        int nextDirection = (direction + 1) % 4;        switch (direction) {            case 0:  // right                if (j < right) {                    dfs(matrix, i, j + 1, direction, result);                } else {                    ++up;                    dfs(matrix, i + 1, j, nextDirection, result);                }                break;            case 1:  // down                if (i < down) {                    dfs(matrix, i+1, j, direction, result);                } else {                    --right;                    dfs(matrix, i, j - 1, nextDirection, result);                }                break;            case 2:  // left                if (j > left) {                    dfs(matrix, i, j - 1, direction, result);                } else {                    --down;                    dfs(matrix, i - 1, j, nextDirection, result);                }                break;            default: // up                if (i > up) {                    dfs(matrix, i - 1, j, direction, result);                } else {                    ++left;                    dfs(matrix, i, j + 1, nextDirection, result);                }        }    }    private int left;    private int right;    private int up;    private int down;}