Google
54 Spiral Matrix

1. Question

Given a matrix ofmxnelements (m rows,n columns), return all elements of the matrix in spiral order.
For example, Given the following matrix:
1
[
2
[ 1, 2, 3 ],
3
[ 4, 5, 6 ],
4
[ 7, 8, 9 ]
5
]
Copied!
You should return[1,2,3,6,9,8,7,4,5].

2. Implementation

1
class Solution {
2
public List<Integer> spiralOrder(int[][] matrix) {
3
List<Integer> res = new ArrayList<>();
4
5
if (matrix == null || matrix.length == 0) {
6
return res;
7
}
8
9
int m = matrix.length, n = matrix[0].length;
10
int rowStart = 0, rowEnd = m - 1, colStart = 0, colEnd = n - 1;
11
12
while (rowStart <= rowEnd && colStart <= colEnd) {
13
for (int j = colStart; j <= colEnd; j++) {
14
res.add(matrix[rowStart][j]);
15
}
16
++rowStart;
17
18
for (int i = rowStart; i <= rowEnd; i++) {
19
res.add(matrix[i][colEnd]);
20
}
21
--colEnd;
22
23
// Edge Case: 当矩阵行数不等于列数时
24
if (rowStart > rowEnd || colStart > colEnd) {
25
break;
26
}
27
28
for (int j = colEnd; j >= colStart; j--) {
29
res.add(matrix[rowEnd][j]);
30
}
31
--rowEnd;
32
33
for (int i = rowEnd; i >= rowStart; i--) {
34
res.add(matrix[i][colStart]);
35
}
36
++colStart;
37
}
38
return res;
39
}
40
}
Copied!

3. Time & Space Complexity

时间复杂度O(m + n), 空间复杂度O(mn)