leetcode: Spiral Matrix

问题描述：

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].

原问题链接：https://leetcode.com/problems/spiral-matrix/

 

问题分析

　　这个问题其实是对矩阵螺旋访问的实现。这里访问的顺序是首先从最上面的行从左到右，然后从最右边的行从上到下，再从最下面的行从右到左，再从最左边的列从下到上。因为每访问完一行或者一列之后，矩阵的范围就缩小了一部分。而且这些能够访问的最左最右以及最上最下的行列将作为后续访问的界限。所以我们可以定义４个变量，rowBegin, rowEnd, colBegin, colEnd分别表示它们行的起始和结束位置，列的起始和结束位置。然后再按照前面要求的顺序螺旋的去访问。当访问完第一行的时候，rowBegin++, 访问完最后一列则colEnd--, 然后依次的rowEnd--, colBegin++。

　　在实现的代码里有一个容易出错的细节，就是当遍历完最上面的第一行以及最右边的列之后，当我们要从最下面行的右边向左遍历以及最左边列的下面向上遍历的时候。我们还是需要判断一下rowBegin <= rowEnd以及colBegin <= colEnd。因为在一些情况下我们前面的访问就已经使得它们的行或者列被访问了，需要避免重复的访问。

　　详细的代码实现如下：

 

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if(matrix.length == 0) return result;
        int rowBegin = 0, rowEnd = matrix.length - 1, colBegin = 0, colEnd = matrix[0].length - 1;
        while(rowBegin <= rowEnd && colBegin <= colEnd) {
            for(int i = colBegin; i <= colEnd; i++) result.add(matrix[rowBegin][i]);
            rowBegin++;
            for(int i = rowBegin; i <= rowEnd; i++) result.add(matrix[i][colEnd]);
            colEnd--;
            if(rowBegin <= rowEnd) {
                for(int i = colEnd; i >= colBegin; i--) result.add(matrix[rowEnd][i]);
            }
            rowEnd--;
            if(colBegin <= colEnd) {
                for(int i = rowEnd; i >= rowBegin; i--) result.add(matrix[i][colBegin]);
            }
            colBegin++;
        }
        return result;
    }
}