import java.util.*;
public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return new ArrayList<Integer>();
        }
        int row = matrix.length;
        int col = matrix[0].length;

        ArrayList<Integer> result = new ArrayList<Integer>();
        //一个矩形,遍历多少圈呢?行数遍历到 row / 2 ,列数呢?col/2
        //5*5 6*6 的矩形都满足这个边界条件
        int start = 0;
        while (row > 2 * start && col > 2 * start ) {
            print(matrix, result, start, row, col);
            start ++;
        }
        return result;

    }
    private void print(int[][] matrix, ArrayList<Integer> result, int start,
                       int row, int col) {
        //左上角x坐标范围
        int startX = start;
        int endX = col - start - 1;
        //右上角开始y坐标范围
        int startY = start;
        int endY = row - start - 1;
        //从左到右
        for (int i = startX; i <= endX; i++) {
            result.add(matrix[startY][i]);
        }
        //从右上到下
        //前提条件 顺时针 startY < endY
        if (startY < endY ) {
            for (int i = startY + 1 ; i <= endY; i++) {
                result.add(matrix[i][endX]);
            }
        }
        //从右下到左下
        //前提条件 顺时针 右上到下 startY < endY
        if (startY < endY && startX < endX ) {
            for (int i = endX - 1; i >= startX ; i--) {
                result.add(matrix[endY][i]);
            }
        }
        //从左下到左上
        //前提条件 顺时针有 右下到左下 startX < endX
        if ( startX < endX && startY < endY - 1 ) {
            for (int i = endY - 1; i > startY; i--) {
                result.add(matrix[i][startX]);
            }
        }
    }
}