题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

样例1

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

样例2

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

算法1

(四指针扫描) $O(n^2)$

1. 从左到右访问第一行，然后top++
2. 从上到下访问最后一列，然后right--
3. 从右到左访问最后一行，然后bottom--

4. 从下到上访问第一列，然后left++

5. 需要注意的是，如果行或列是奇数，上下指针或者左右指针可能会重叠起来，且在读入最中间那一行(列)的时候可能会读错，需要特判一下

时间复杂度：$O(n)$，所有元素都遍历一次

Java 代码

class Solution {
    public List<Integer> spiralOrder(int[][] g) {
        if(g == null || g.length == 0 || g[0].length == 0) return new ArrayList<>();
        int m = g.length;
        int n = g[0].length;
        int u = 0, d = m-1, l = 0, r = n-1;
        List<Integer> res = new ArrayList<>();
        while(u <= d && l <= r){
            for(int i = l; i <= r; i++) res.add(g[u][i]);
            u++;
            for(int i = u; i <= d; i++) res.add(g[i][r]);
            r--;
            if(u > d || r < l) break;
            for(int i = r; i >= l; i--) res.add(g[d][i]);
            d--;
            for(int i = d; i >= u; i--) res.add(g[i][l]);
            l++;
        }
        return res;
    }
}