剑指 Offer 29. 顺时针打印矩阵

港控/mmm° 2022-11-20 09:35 83阅读 0赞

# 题目 #

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

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

示例 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][https_leetcode-cn.com_problems_shun-shi-zhen-da-yin-ju-zhen-lcof]

# 解题思路 #

矩阵为空时需特判  
定义四个边界左,上,右,下,顺时针打印的顺序:

*  从左到右
 *  从上到下
 *  从右到左
 *  从下到上

每个方向的打印需要做三件事:

*  打印当前下标的值
 *  边界收缩
 *  判断打印是否结束

<table> 
 <thead> 
  <tr> 
   <th>打印方向</th> 
   <th>打印当前下标的值</th> 
   <th>边界收缩</th> 
   <th>判断打印是否结束</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>从左到右<br>l -&gt; r</td> 
   <td>当前行t不变,列递增</td> 
   <td>上边界收缩<br>t + 1</td> 
   <td>上边界 &gt; 下边界<br>t &gt; b</td> 
  </tr> 
  <tr> 
   <td>从上到下<br>t -&gt; b</td> 
   <td>当前列r不变,行递增</td> 
   <td>右边界收缩<br>r - 1</td> 
   <td>左边界 &gt; 右边界<br>l &gt; r</td> 
  </tr> 
  <tr> 
   <td>从右到左<br>r -&gt; l</td> 
   <td>当前行b不变,列递减</td> 
   <td>下边界收缩<br>b - 1</td> 
   <td>上边界 &gt; 下边界<br>t &gt; b</td> 
  </tr> 
  <tr> 
   <td>从下到上<br>b -&gt; t</td> 
   <td>当前列l不变,行递减</td> 
   <td>左边界收缩<br>l + 1</td> 
   <td>左边界 &gt; 右边界<br>l &gt; r</td> 
  </tr> 
 </tbody> 
</table>

# 代码 #

class Solution { 
        public int[] spiralOrder(int[][] matrix) { 
            // 特殊情况判断
            if (matrix.length == 0) { 
                return new int[0];
            }
    
            // 定义左,上,右,下,四个边界
            int l = 0;
            int t = 0;
            int r = matrix[0].length - 1;
            int b = matrix.length - 1;
            // 返回的数组
            int[] result = new int[(r + 1) * (b + 1)];
            // 数组赋值的下标
            int index = 0;
            while (true) { 
                // 从左到右,当前行不变t,列++
                for (int i = l; i <= r; i++) { 
                    result[index++] = matrix[t][i];
                }
                // 这里是两步
                // 1.边界收缩: t + 1
                // 2.判断打印是否结束: t > b(上边界是否大于下边界)
                if (++t > b) { 
                    break;
                }
    
                // 从上到下,当前列不变r,行++
                for (int i = t; i <= b; i++) { 
                    result[index++] = matrix[i][r];
                }
                // 1.边界收缩: r - 1
                // 2.判断打印是否结束: l > r(左边界是否大于右边界)
                if (l > --r) { 
                    break;
                }
    
                // 从右到左,当前行不变b,列--
                for (int i = r; i >= l; i--) { 
                    result[index++] = matrix[b][i];
                }
                // 1.边界收缩: b - 1
                // 2.判断打印是否结束: t > b(上边界是否大于下边界)
                if (t > --b) { 
                    break;
                }
    
                // 从下到上,当前列不变l,行--
                for (int i = b; i >= t; i--) { 
                    result[index++] = matrix[i][l];
                }
                // 1.边界收缩: l + 1
                // 2.判断打印是否结束: l > r(左边界是否大于右边界)
                if (++l > r) { 
                    break;
                }
            }
            return result;  
        }
    }

# 复杂度 #

*  时间复杂度:O(mn),m,n为矩阵的行数和列数
 *  空间复杂度:O(1),边界占用常数级额外空间

[https_leetcode-cn.com_problems_shun-shi-zhen-da-yin-ju-zhen-lcof]: https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof