每天一题LeetCode【第39天】

T54. Spiral Matrix【Medium】

题目

给一个 m × n 的矩阵（m 行，n 列），按螺旋顺序返回所有元素。

例如，

给出如下矩阵：

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

你应该返回： [1,2,3,6,9,8,7,4,5]

思路

看到这道题我的反应是递归什么的，然而当我看到 Top Solution 的时候，仿佛打开了新世界的大门，虽然说代码很长，但是，差不多一看就知道代码的意思，因为它就是完美契合了我们不用代码解决这个问题的思路。

就是，哈哈： 拿只笔画圈圈！

你没有看错，你只要像我这样画一个这么难看的图片，这就是本题的思路了！

画圈圈时有两个点:

① 画完一行（列），下次再到这行（列）时会画它的内圈

② 当画到最后，两线不能相交（就是下面的 boundriesCrossed 的作用）

代码

代码取自 Top Solution，稍作注释

public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> spiralList = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0) return spiralList;
        // 设置初始值
        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;

        while(true){
            // 画上面的那行
            for(int j=left; j <=right;j++){
                spiralList.add(matrix[top][j]);
            }
            //下一次内行
            top++;
            //每画一行(列) 判断下一行(列)有没有越界,有的话跳出循环
            if(boundriesCrossed(left,right,bottom,top))
                break;

            // 画最右边的列
            for(int i=top; i <= bottom; i++){
                spiralList.add(matrix[i][right]);
            }
            //下一次内列
            right--;
            if(boundriesCrossed(left,right,bottom,top))
                break;

            //画下面的那行
            for(int j=right; j >=left; j--){
                spiralList.add(matrix[bottom][j]);
            }
            //下一次内行
            bottom--;
            if(boundriesCrossed(left,right,bottom,top))
                break;

            //画左边的列
            for(int i=bottom; i >= top; i--){
                spiralList.add(matrix[i][left]);
            }
            //下一次内列
            left++;
            if(boundriesCrossed(left,right,bottom,top))
                break;
        }

        return spiralList;
    }

    //每画一行(列) 判断下一行(列)有没有越界,有的话跳出循环
public boolean boundriesCrossed(int left,int right,int bottom,int top){
     if(left>right || bottom<top)
         return true;
     else
         return false;
    }