花式遍历.md

# 二维数组的花式遍历

<p align='center'>
<a href="https://github.com/labuladong/fucking-algorithm" target="view_window"><img alt="GitHub" src="https://img.shields.io/github/stars/labuladong/fucking-algorithm?label=Stars&style=flat-square&logo=GitHub"></a>
<a href="https://appktavsiei5995.pc.xiaoe-tech.com/index" target="_blank"><img class="my_header_icon" src="https://img.shields.io/static/v1?label=精品课程&message=查看&color=pink&style=flat"></a>
<a href="https://www.zhihu.com/people/labuladong"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@labuladong-000000.svg?style=flat-square&logo=Zhihu"></a>
<a href="https://space.bilibili.com/14089380"><img src="https://img.shields.io/badge/B站-@labuladong-000000.svg?style=flat-square&logo=Bilibili"></a>
</p>

![](https://labuladong.github.io/algo/images/souyisou1.png)

**通知：[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.0；[第 13 期刷题打卡](https://mp.weixin.qq.com/s/eUG2OOzY3k_ZTz-CFvtv5Q) 最后几天报名！另外，建议你在我的 [网站](https://labuladong.github.io/algo/) 学习文章，体验更好。**



读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [151. Reverse Words in a String](https://leetcode.com/problems/reverse-words-in-a-string/) | [151. 翻转字符串里的单词](https://leetcode.cn/problems/reverse-words-in-a-string/) | 🟠
| [48. Rotate Image](https://leetcode.com/problems/rotate-image/) | [48. 旋转图像](https://leetcode.cn/problems/rotate-image/) | 🟠
| [54. Spiral Matrix](https://leetcode.com/problems/spiral-matrix/) | [54. 螺旋矩阵](https://leetcode.cn/problems/spiral-matrix/) | 🟠
| [59. Spiral Matrix II](https://leetcode.com/problems/spiral-matrix-ii/) | [59. 螺旋矩阵 II](https://leetcode.cn/problems/spiral-matrix-ii/) | 🟠
| - | [剑指 Offer 29. 顺时针打印矩阵](https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/) | 🟢

**-----------**

有不少读者说，看过很多公众号历史文章之后，掌握了框架思维，可以解决大部分有套路框架可循的题目。

但是框架思维也不是万能的，有一些特定技巧呢，属于会者不难，难者不会的类型，只能通过多刷题进行总结和积累。

那么本文我分享一些巧妙的二维数组的花式操作，你只要有个印象，以后遇到类似题目就不会懵圈了。

### 顺/逆时针旋转矩阵

对二维数组进行旋转是常见的笔试题，力扣第 48 题「旋转图像」就是很经典的一道：

![](https://labuladong.github.io/algo/images/花式遍历/title.png)

题目很好理解，就是让你将一个二维矩阵顺时针旋转 90 度，**难点在于要「原地」修改**，函数签名如下：

```java
void rotate(int[][] matrix)
```

如何「原地」旋转二维矩阵？稍想一下，感觉操作起来非常复杂，可能要设置巧妙的算法机制来「一圈一圈」旋转矩阵：

![](https://labuladong.github.io/algo/images/花式遍历/1.png)

**但实际上，这道题不能走寻常路**，在讲巧妙解法之前，我们先看另一道谷歌曾经考过的算法题热热身：

给你一个包含若干单词和空格的字符串 `s`，请你写一个算法，**原地**反转所有单词的顺序。

比如说，给你输入这样一个字符串：

```shell
s = "hello world labuladong"
```

你的算法需要**原地**反转这个字符串中的单词顺序：

```shell
s = "labuladong world hello"
```

常规的方式是把 `s` 按空格 `split` 成若干单词，然后 `reverse` 这些单词的顺序，最后把这些单词 `join` 成句子。但这种方式使用了额外的空间，并不是「原地反转」单词。

**正确的做法是，先将整个字符串 `s` 反转**：

```shell
s = "gnodalubal dlrow olleh"
```

**然后将每个单词分别反转**：

```shell
s = "labuladong world hello"
```

这样，就实现了原地反转所有单词顺序的目的。力扣第 151 题「颠倒字符串中的单词」就是类似的问题，你可以顺便去做一下。

我讲这道题的目的是什么呢？

**旨在说明，有时候咱们拍脑袋的常规思维，在计算机看来可能并不是最优雅的；但是计算机觉得最优雅的思维，对咱们来说却不那么直观**。也许这就是算法的魅力所在吧。

回到之前说的顺时针旋转二维矩阵的问题，常规的思路就是去寻找原始坐标和旋转后坐标的映射规律，但我们是否可以让思维跳跃跳跃，尝试把矩阵进行反转、镜像对称等操作，可能会出现新的突破口。

**我们可以先将 `n x n` 矩阵 `matrix` 按照左上到右下的对角线进行镜像对称**：

![](https://labuladong.github.io/algo/images/花式遍历/2.jpeg)

**然后再对矩阵的每一行进行反转**：

![](https://labuladong.github.io/algo/images/花式遍历/3.jpeg)

**发现结果就是 `matrix` 顺时针旋转 90 度的结果**：

![](https://labuladong.github.io/algo/images/花式遍历/4.jpeg)

将上述思路翻译成代码，即可解决本题：

```java
// 将二维矩阵原地顺时针旋转 90 度
public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 先沿对角线镜像对称二维矩阵
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // swap(matrix[i][j], matrix[j][i]);
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // 然后反转二维矩阵的每一行
    for (int[] row : matrix) {
        reverse(row);
    }
}

// 反转一维数组
void reverse(int[] arr) {
    int i = 0, j = arr.length - 1;
    while (j > i) {
        // swap(arr[i], arr[j]);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
}
```

肯定有读者会问，如果没有做过这道题，怎么可能想到这种思路呢？

仔细想想，旋转二维矩阵的难点在于将「行」变成「列」，将「列」变成「行」，而只有按照对角线的对称操作是可以轻松完成这一点的，对称操作之后就很容易发现规律了。

**既然说道这里，我们可以发散一下，如何将矩阵逆时针旋转 90 度呢**？

思路是类似的，只要通过另一条对角线镜像对称矩阵，然后再反转每一行，就得到了逆时针旋转矩阵的结果：

![](https://labuladong.github.io/algo/images/花式遍历/5.jpeg)

翻译成代码如下：

```java
// 将二维矩阵原地逆时针旋转 90 度
void rotate2(int[][] matrix) {
    int n = matrix.length;
    // 沿左下到右上的对角线镜像对称二维矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            // swap(matrix[i][j], matrix[n-j-1][n-i-1])
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - j - 1][n - i - 1];
            matrix[n - j - 1][n - i - 1] = temp;
        }
    }
    // 然后反转二维矩阵的每一行
    for (int[] row : matrix) {
        reverse(row);
    }
}

void reverse(int[] arr) { /* 见上文 */}
```

至此，旋转矩阵的问题就解决了。

### 矩阵的螺旋遍历

我的公众号动态规划系列文章经常需要遍历二维 `dp` 数组，但难点在于状态转移方程而不是数组的遍历，顶多就是倒序遍历。

但接下来我们讲一下力扣第 54 题「螺旋矩阵」，看一看二维矩阵可以如何花式遍历：

![](https://labuladong.github.io/algo/images/花式遍历/title2.png)

函数签名如下：

```java
List<Integer> spiralOrder(int[][] matrix)
```

**解题的核心思路是按照右、下、左、上的顺序遍历数组，并使用四个变量圈定未遍历元素的边界**：

![](https://labuladong.github.io/algo/images/花式遍历/6.png)

随着螺旋遍历，相应的边界会收缩，直到螺旋遍历完整个数组：

![](https://labuladong.github.io/algo/images/花式遍历/7.png)

只要有了这个思路，翻译出代码就很容易了：

```java
List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int upper_bound = 0, lower_bound = m - 1;
    int left_bound = 0, right_bound = n - 1;
    List<Integer> res = new LinkedList<>();
    // res.size() == m * n 则遍历完整个数组
    while (res.size() < m * n) {
        if (upper_bound <= lower_bound) {
            // 在顶部从左向右遍历
            for (int j = left_bound; j <= right_bound; j++) {
                res.add(matrix[upper_bound][j]);
            }
            // 上边界下移
            upper_bound++;
        }
        
        if (left_bound <= right_bound) {
            // 在右侧从上向下遍历
            for (int i = upper_bound; i <= lower_bound; i++) {
                res.add(matrix[i][right_bound]);
            }
            // 右边界左移
            right_bound--;
        }
        
        if (upper_bound <= lower_bound) {
            // 在底部从右向左遍历
            for (int j = right_bound; j >= left_bound; j--) {
                res.add(matrix[lower_bound][j]);
            }
            // 下边界上移
            lower_bound--;
        }
        
        if (left_bound <= right_bound) {
            // 在左侧从下向上遍历
            for (int i = lower_bound; i >= upper_bound; i--) {
                res.add(matrix[i][left_bound]);
            }
            // 左边界右移
            left_bound++;
        }
    }
    return res;
}
```

力扣第 59 题「螺旋矩阵 II」也是类似的题目，只不过是反过来，让你按照螺旋的顺序生成矩阵：

![](https://labuladong.github.io/algo/images/花式遍历/title3.png)

函数签名如下：

```java
int[][] generateMatrix(int n)
```

有了上面的铺垫，稍微改一下代码即可完成这道题：

```java
int[][] generateMatrix(int n) {
    int[][] matrix = new int[n][n];
    int upper_bound = 0, lower_bound = n - 1;
    int left_bound = 0, right_bound = n - 1;
    // 需要填入矩阵的数字
    int num = 1;
    
    while (num <= n * n) {
        if (upper_bound <= lower_bound) {
            // 在顶部从左向右遍历
            for (int j = left_bound; j <= right_bound; j++) {
                matrix[upper_bound][j] = num++;
            }
            // 上边界下移
            upper_bound++;
        }
        
        if (left_bound <= right_bound) {
            // 在右侧从上向下遍历
            for (int i = upper_bound; i <= lower_bound; i++) {
                matrix[i][right_bound] = num++;
            }
            // 右边界左移
            right_bound--;
        }
        
        if (upper_bound <= lower_bound) {
            // 在底部从右向左遍历
            for (int j = right_bound; j >= left_bound; j--) {
                matrix[lower_bound][j] = num++;
            }
            // 下边界上移
            lower_bound--;
        }
        
        if (left_bound <= right_bound) {
            // 在左侧从下向上遍历
            for (int i = lower_bound; i >= upper_bound; i--) {
                matrix[i][left_bound] = num++;
            }
            // 左边界右移
            left_bound++;
        }
    }
    return matrix;
}
```

至此，两道螺旋矩阵的题目也解决了。

以上就是遍历二维数组的一些技巧，其他数组技巧可参见之前的文章 [前缀和数组](https://labuladong.github.io/article/fname.html?fname=前缀和技巧)，[差分数组](https://labuladong.github.io/article/fname.html?fname=差分技巧)，[数组双指针算法集合](https://labuladong.github.io/article/fname.html?fname=链表技巧)。 

> 最后打个广告，我亲自制作了一门 [数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO)，以视频课为主，手把手带你实现常用的数据结构及相关算法，旨在帮助算法基础较为薄弱的读者深入理解常用数据结构的底层原理，在算法学习中少走弯路。




<hr>
<details>
<summary><strong>引用本文的题目</strong></summary>

<strong>安装 [我的 Chrome 刷题插件](https://mp.weixin.qq.com/s/X-fE9sR4BLi6T9pn7xP4pg) 点开下列题目可直接查看解题思路：</strong>

| LeetCode | 力扣 |
| :----: | :----: |
| [1260. Shift 2D Grid](https://leetcode.com/problems/shift-2d-grid/?show=1) | [1260. 二维网格迁移](https://leetcode.cn/problems/shift-2d-grid/?show=1) |

</details>



**＿＿＿＿＿＿＿＿＿＿＿＿＿**

**《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「**进群**」可加入算法群；回复「**全家桶**」可下载配套 PDF 和刷题全家桶**：

![](https://labuladong.github.io/algo/images/souyisou2.png)