题目
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1:
1
2 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]示例 2:
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]限制:
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
一开始我的思路偏向于 event driven,每次遇到右侧 block 的情况就向下走,类似状态转移,为了记录下一个位置是否访问过还需要一个数组来记录。为了实现以上想法试图用递归实现,但是并没有考虑到每次顺时针打印的顺序都是右、下、左、上。
其实如果考虑到顺序是固定的,并且每沿着一个方向走到头都可以正确判断是否结束,我们完全可以记录沿此方向剩余需要访问的元素个数,节省空间。
因此,思路如下:
- 从左上角开始,向右走到头,此时第一行不会再被访问,移除
- 向下走到头,此时最右侧列不会再被访问,移除
- 向左走到头,此时最下面一行不会再被访问,移除
- 向上走到头,此时最左侧一列不会再被访问,移除
- 以上每一步结束都需要判断是否有两条边界重合,重合时不再有元素需要访问,退出
- 循环以上步骤直至结束
1 | class Solution { |
- 时间复杂度$O(MN)$
- 空间复杂度$O(1)$