Given a matrix of m x 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].
題意就是給定一個(gè)二維數(shù)組逐哈，輸出從外向里走過(guò)的路徑。
自己的做法是定義一個(gè)方向數(shù)組看政，從向右開(kāi)始遍歷婉宰；用一個(gè)二維數(shù)組記錄已經(jīng)走過(guò)的點(diǎn)湘纵；當(dāng)下一個(gè)點(diǎn)到了邊界或者是已經(jīng)走過(guò)的點(diǎn)就改變方向；循環(huán)退出條件是走過(guò)了所有數(shù)組中的點(diǎn)。

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return res;
    }

    int row = matrix.length;
    int col = matrix[0].length;
    int directionIndex = 0;
    String[] directions = {"right", "down", "left", "up"};
    int[] pos = {0, 0};
    int cnt = 0;
    int total = row * col;
    while (cnt < total) {
        res.add(matrix[pos[0]][pos[1]]);
        matrix[pos[0]][pos[1]] = Integer.MAX_VALUE;
        String direction = directions[directionIndex % directions.length];
        switch (direction) {
            case "right":
                if (pos[1] < col - 1 && matrix[pos[0]][pos[1] + 1] != Integer.MAX_VALUE) {
                    pos[1]++;
                } else {
                    directionIndex++;
                    pos[0]++;
                }
                break;
            case "down":
                if (pos[0] < row - 1 && matrix[pos[0] + 1][pos[1]] != Integer.MAX_VALUE) {
                    pos[0]++;
                } else {
                    directionIndex++;
                    pos[1]--;
                }
                break;
            case "left":
                if (pos[1] > 0 && matrix[pos[0]][pos[1] - 1] != Integer.MAX_VALUE) {
                    pos[1]--;
                } else {
                    directionIndex++;
                    pos[0]--;
                }
                break;
            case "up":
                if (pos[0] > 0 && matrix[pos[0] - 1][pos[1]] != Integer.MAX_VALUE) {
                    pos[0]--;
                } else {
                    directionIndex++;
                    pos[1]++;
                }
                break;
        }
        cnt++;
    }

    return res;
}

discuss中有一種解法非常好岔乔，它把這道題看成是在一個(gè)圍欄里面不斷向里走，每次走完一行或者一列滚躯，這個(gè)圍欄就會(huì)向內(nèi)縮小雏门。

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<Integer>();
    if (matrix.length == 0) {
        return res;
    }
    
    int rowBegin = 0;
    int rowEnd = matrix.length-1;
    int colBegin = 0;
    int colEnd = matrix[0].length - 1;
    
    while (rowBegin <= rowEnd && colBegin <= colEnd) {
        // Traverse Right
        for (int j = colBegin; j <= colEnd; j ++) {
            res.add(matrix[rowBegin][j]);
        }
        rowBegin++;
        
        // Traverse Down
        for (int j = rowBegin; j <= rowEnd; j ++) {
            res.add(matrix[j][colEnd]);
        }
        colEnd--;
        
        if (rowBegin <= rowEnd) {
            // Traverse Left
            for (int j = colEnd; j >= colBegin; j --) {
                res.add(matrix[rowEnd][j]);
            }
        }
        rowEnd--;
        
        if (colBegin <= colEnd) {
            // Traver Up
            for (int j = rowEnd; j >= rowBegin; j --) {
                res.add(matrix[j][colBegin]);
            }
        }
        colBegin ++;
    }
    
    return res;
}