54. 螺旋矩阵

1. 题目

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

img

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

img

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

2. 思路

  • 已知题目需要顺时针转弯，因此需要有一个转弯的思路，怎么转弯并且保证转弯之后的方向持续不变直至下标越界或该值已读取
  • 由上述思路首先衍生出2个小问题，一个是判断下标是正常下标，第二个是判断该值已经被读取
    • 针对判断下标可结合matrix二维数组得到行数与列数，从而进行下标合法性的判断
    • 针对判断数值是否已读取过，可读取过后将该值设置为其他变量（如Integer.MAX_VALUE），以表示该值已读取
  • 要进行方向的扭转，可配合二维数组实现，首先可以通过官方图示知道螺旋矩阵读取一共会出现四个方向，分别是：右 -> 下 -> 左 -> 上
  • 以上方向的转动无非是下标的转动，那么通过定义出代表方向的二维数组代表四个方向的下标移动方向
  • 如direction = {0, 1}代表向右移动1个单位，row + direction[0]即可得到下一个行坐标，column + direction[1]即可得到下一个列坐标
  • 在出现下标越界或出现该值标记为已读取时，则进行转弯操作
  • 因为转弯的方向会循环持续为: 右 -> 下 -> 左 -> 上 -> 右 -> 下 -> …，而代表方向的二维数组DIRECTIONS只有四个子数值，因此代表方向的下标directionIndex将采取取余+1的方式来确保达到循环的效果
    • 即新的方向下标为：directionIndex = (directionIndex + 1) % 4

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private static final int VISITED = Integer.MAX_VALUE;
    private int totalRows = 0;
    private int totalColumns = 0;

    public List<Integer> spiralOrder(int[][] matrix) {
        var result = new ArrayList<Integer>();
        totalRows = matrix.length;
        totalColumns = matrix[0].length;
        var row = 0;
        var column = 0;
        var directionIndex = 0;
        var matrixSize = totalColumns * totalRows;

        while (result.size() != matrixSize) {
            if(matrix[row][column] != VISITED){
                result.add(matrix[row][column]);
                matrix[row][column] = VISITED;
            }

            var direction = DIRECTIONS[directionIndex];

            var nextRow = row + direction[0];
            var nextColumn = column + direction[1];
            if (!isValid(nextRow, nextColumn) || matrix[nextRow][nextColumn] == VISITED) {
                directionIndex = (directionIndex + 1) % 4;
                continue;
            }

            row = nextRow;
            column = nextColumn;
        }

        return result;
    }

    private boolean isValid(int row, int column) {
        return row >= 0 && row < totalRows && column >= 0 && totalColumns > column;
    }
}

4. 复杂度

  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

image-20230821225503575