package DataStructure.array;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵 https://leetcode.cn/problems/spiral-matrix
 * 题目简述:给定一个m*n的二维数组,从matrix[0][0]开始顺时针螺旋打印数组
 */
public class SpiralOrder {

 public static void main(String[] args) {
 new SpiralOrder().spiralOrder(new int[][]{{7},{9}, {6}});
 }

 /**
 * 思路:要走的圈数为Math.min((m>>1) + m%2, (n>>1) + n%2),第k圈的圈首即为i = k,j = k,并计算圈长宽
 * 先加入圈首,然后根据长宽顺时针走一圈,注意矩阵宽度大于1才能向左走,矩阵长度大于1才能向上走
 */
 public List<Integer> spiralOrder(int[][] matrix) {
 int m = matrix.length, n = matrix[0].length;
 List<Integer> result = new ArrayList<>(m*n);
 int turnTimes = Math.min((m>>1) + m%2, (n>>1) + n%2); //要走的圈数
 for (int k = 0;k < turnTimes;k++) {
 int i = k, j = k, len = n-2*k, wid = m-2*k;
 result.add(matrix[i][j]);
 //向右
 for (int t = 1;t < len;t++)
 result.add(matrix[i][++j]);
 //向下
 for (int t = 1;t < wid;t++)
 result.add(matrix[++i][j]);
 //向左,矩阵宽度大于1才能向左走
 for (int t = 1;wid > 1 && t < len;t++)
 result.add(matrix[i][--j]);
 //向上,矩阵长度大于1才能向上走
 for (int t = 1;len > 1 && t < wid-1;t++)
 result.add(matrix[--i][j]);
 }
 return result;
 }
}