高频数组

合并区间

合并区间是什么？

给你一堆区间，比如：

[[1,3], [2,6], [8,10], [15,18]]

其中 [1,3] 和 [2,6] 有重叠，所以要合并成 [1,6]。

最后答案是：

[[1,6], [8,10], [15,18]]

核心思路

先按每个区间的左端点 start 从小到大排序。

排序后，只需要看“当前区间”和“答案里最后一个区间”能不能合并：

如果 currentStart <= lastEnd
说明重叠，可以合并

如果 currentStart > lastEnd
说明不重叠，直接加入答案

C# 代码

using System; // 引入基础命名空间

using System.Collections.Generic; // 引入 List 集合命名空间

public class Solution // 定义题解类
{ // 类开始
    public int[][] Merge(int[][] intervals) // 定义合并区间方法，输入二维数组，输出二维数组
    { // 方法开始
        if (intervals == null || intervals.Length == 0) // 判断输入是否为空
        { // if 开始
            return Array.Empty<int[]>(); // 返回空数组
        } // if 结束

        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0])); // 按每个区间的左端点从小到大排序

        List<int[]> result = new List<int[]>(); // 创建结果列表，用来保存合并后的区间

        result.Add(intervals[0]); // 先把排序后的第一个区间放进结果里

        for (int i = 1; i < intervals.Length; i++) // 从第二个区间开始遍历
        { // for 开始
            int[] last = result[result.Count - 1]; // 取出结果列表中的最后一个区间

            int[] current = intervals[i]; // 取出当前正在处理的区间

            if (current[0] <= last[1]) // 如果当前区间左端点小于等于上一个区间右端点，说明重叠
            { // if 开始
                last[1] = Math.Max(last[1], current[1]); // 合并区间，右端点取两者最大值
            } // if 结束
            else // 如果不重叠
            { // else 开始
                result.Add(current); // 当前区间不能合并，直接加入结果列表
            } // else 结束
        } // for 结束

        return result.ToArray(); // 把 List 转成二维数组返回
    } // 方法结束
} // 类结束

复杂度

时间复杂度：O(n log n)，主要花在排序上。

空间复杂度：O(n)，最坏情况下所有区间都不重叠，结果里要保存所有区间。

一句话记忆

IMPORTANT

合并区间就是：先按左端点排序，再从左到右扫描，能合就扩右边界，不能合就新开一个区间。

旋转数组

旋转数组是什么？

旋转数组通常指：一个原本升序的数组，被从某个位置切开后，把后半段搬到前面。

比如原数组：

[1, 2, 3, 4, 5, 6, 7]

旋转后可能变成：

[4, 5, 6, 7, 1, 2, 3]

它不是乱序，而是由两个升序段组成。

常见考法

最常考的是：搜索旋转排序数组。

题目一般是：

给你一个旋转后的升序数组 nums 和一个 target，
要求返回 target 的下标，找不到返回 -1。

例如：

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
答案 = 4

核心思路

虽然整个数组不是完全升序，但每次二分时，左右两边一定至少有一边是有序的。

比如：

[4, 5, 6, 7, 0, 1, 2]
 left     mid         right

nums[left] <= nums[mid]，说明左半边是有序的。

然后判断 target 是否落在左半边范围内：

nums[left] <= target < nums[mid]

如果在，就去左边找。

如果不在，就去右边找。

C# 代码

public class Solution // 定义题解类
{ // 类开始
    public int Search(int[] nums, int target) // 定义搜索方法，输入数组和目标值，返回目标下标
    { // 方法开始
        int left = 0; // 定义左指针，初始指向数组开头

        int right = nums.Length - 1; // 定义右指针，初始指向数组末尾

        while (left <= right) // 当搜索区间仍然有效时继续二分
        { // while 开始
            int mid = left + (right - left) / 2; // 计算中间下标，避免 left + right 溢出

            if (nums[mid] == target) // 如果中间值正好等于目标值
            { // if 开始
                return mid; // 直接返回目标下标
            } // if 结束

            if (nums[left] <= nums[mid]) // 如果左半边是有序的
            { // if 开始
                if (nums[left] <= target && target < nums[mid]) // 如果目标值落在左半边范围内
                { // if 开始
                    right = mid - 1; // 缩小到左半边继续搜索
                } // if 结束
                else // 如果目标值不在左半边范围内
                { // else 开始
                    left = mid + 1; // 去右半边继续搜索
                } // else 结束
            } // if 结束
            else // 如果左半边无序，那么右半边一定有序
            { // else 开始
                if (nums[mid] < target && target <= nums[right]) // 如果目标值落在右半边范围内
                { // if 开始
                    left = mid + 1; // 缩小到右半边继续搜索
                } // if 结束
                else // 如果目标值不在右半边范围内
                { // else 开始
                    right = mid - 1; // 去左半边继续搜索
                } // else 结束
            } // else 结束
        } // while 结束

        return -1; // 循环结束仍没找到，返回 -1
    } // 方法结束
} // 类结束

复杂度

时间复杂度：O(log n)，因为每次都排除一半。

空间复杂度：O(1)，只用了几个指针变量。

一句话记忆

NOTE

旋转数组二分的关键是：每次判断哪一半有序，再看 target 在不在有序那半。

移动零

移动零是什么？

题目通常是：

给你一个数组 nums，把所有 0 移动到数组末尾，同时保持非零元素的相对顺序不变。

例如：

输入：[0, 1, 0, 3, 12]
输出：[1, 3, 12, 0, 0]

核心思路

用双指针：

fast：从左到右扫描数组。

slow：表示下一个非零元素应该放的位置。

遇到非零数，就把它放到 slow 位置，然后 slow++。

第一轮结束后，slow 前面都是非零数。

第二轮从 slow 到数组末尾全部补 0。

C# 代码

public class Solution // 定义题解类
{ // 类开始
    public void MoveZeroes(int[] nums) // 定义移动零方法，直接修改原数组
    { // 方法开始
        int slow = 0; // slow 表示下一个非零元素应该放的位置

        for (int fast = 0; fast < nums.Length; fast++) // fast 从左到右扫描整个数组
        { // for 开始
            if (nums[fast] != 0) // 如果当前元素不是 0
            { // if 开始
                nums[slow] = nums[fast]; // 把当前非零元素放到 slow 指向的位置

                slow++; // slow 后移，准备放下一个非零元素
            } // if 结束
        } // for 结束

        for (int i = slow; i < nums.Length; i++) // 从 slow 开始，把后面的位置全部补成 0
        { // for 开始
            nums[i] = 0; // 当前下标写入 0
        } // for 结束
    } // 方法结束
} // 类结束

复杂度

时间复杂度：O(n)，数组只遍历两次。

空间复杂度：O(1)，原地修改，没有额外数组。

一句话记忆

TIP

移动零就是：fast 找非零，slow 放非零，最后 slow 后面全部补 0。

最大子数组和

最大子数组和是什么？

题目通常是：

给你一个整数数组 nums，找出一个连续子数组，使它的和最大，返回这个最大和。

例如：

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

最大连续子数组是：

[4, -1, 2, 1]

最大和是：

6

核心思路

用 Kadane 算法，也可以理解成动态规划。

维护两个变量：

current：以当前元素结尾的最大子数组和。

best：目前为止出现过的最大子数组和。

每次看当前数字 nums[i] 时，只做一个选择：

要么接在前面的子数组后面
要么从当前数字重新开始

状态转移：

current = Max(nums[i], current + nums[i])
best = Max(best, current)

C# 代码

using System; // 引入 System 命名空间，用来使用 Math.Max

public class Solution // 定义题解类
{ // 类开始
    public int MaxSubArray(int[] nums) // 定义最大子数组和方法，输入数组，返回最大连续子数组和
    { // 方法开始
        int current = nums[0]; // current 表示以当前位置结尾的最大子数组和，初始为第一个数

        int best = nums[0]; // best 表示目前遇到的全局最大子数组和，初始为第一个数

        for (int i = 1; i < nums.Length; i++) // 从第二个元素开始遍历数组
        { // for 开始
            current = Math.Max(nums[i], current + nums[i]); // 判断是从当前数重新开始，还是接在前面的子数组后面

            best = Math.Max(best, current); // 用 current 更新全局最大值 best
        } // for 结束

        return best; // 返回最大子数组和
    } // 方法结束
} // 类结束

为什么这样是对的？

如果前面的 current 是负数，那么它接到当前数字前面只会拖后腿。

比如：

current = -3
nums[i] = 4

那肯定选：

4

而不是：

-3 + 4 = 1

所以每一步只需要判断：前面的和有没有价值。

复杂度

时间复杂度：O(n)，只遍历一次数组。

空间复杂度：O(1)，只用了两个变量。

一句话记忆

WARNING

最大子数组和就是：current 负责局部最优，best 负责全局最优；前面拖后腿就从当前数重新开始。

接雨水

接雨水是什么？

题目通常是：

给你一个数组 height，每个数表示柱子的高度。
下雨后，问这些柱子之间最多能接多少水。

例如：

height = [0,1,0,2,1,0,1,3,2,1,2,1]

答案是：

6

核心思路

一个位置能接多少水，取决于它左边最高的柱子和右边最高的柱子。

公式是：

当前位置水量 = min(左边最高, 右边最高) - 当前高度

但我们不用真的为每个位置都提前算左右最高，可以用双指针优化到 O(1) 空间。

为什么双指针可以？

准备两个指针：

left 从左边走。

right 从右边走。

再维护：

leftMax：左边目前见过的最高柱子。

rightMax：右边目前见过的最高柱子。

每次比较：

height[left] 和 height[right]

哪边更矮，就先处理哪边。

因为水位由短板决定，矮的一边已经能确定当前最多接多少水。

C# 代码

using System; // 引入 System 命名空间

public class Solution // 定义题解类
{ // 类开始
    public int Trap(int[] height) // 定义接雨水方法，输入高度数组，返回总水量
    { // 方法开始
        int left = 0; // 定义左指针，初始指向数组最左边

        int right = height.Length - 1; // 定义右指针，初始指向数组最右边

        int leftMax = 0; // 记录从左到右目前见过的最高柱子

        int rightMax = 0; // 记录从右到左目前见过的最高柱子

        int water = 0; // 记录最终能接到的总水量

        while (left < right) // 当左右指针还没有相遇时继续处理
        { // while 开始
            if (height[left] < height[right]) // 如果左边柱子比右边柱子矮，先处理左边
            { // if 开始
                if (height[left] >= leftMax) // 如果当前左柱子刷新了左侧最高高度
                { // if 开始
                    leftMax = height[left]; // 更新 leftMax
                } // if 结束
                else // 如果当前左柱子低于左侧最高高度
                { // else 开始
                    water += leftMax - height[left]; // 当前格子能接 leftMax 和当前高度的差值
                } // else 结束

                left++; // 左指针向右移动
            } // if 结束
            else // 如果右边柱子更矮或一样高，先处理右边
            { // else 开始
                if (height[right] >= rightMax) // 如果当前右柱子刷新了右侧最高高度
                { // if 开始
                    rightMax = height[right]; // 更新 rightMax
                } // if 结束
                else // 如果当前右柱子低于右侧最高高度
                { // else 开始
                    water += rightMax - height[right]; // 当前格子能接 rightMax 和当前高度的差值
                } // else 结束

                right--; // 右指针向左移动
            } // else 结束
        } // while 结束

        return water; // 返回总接水量
    } // 方法结束
} // 类结束

复杂度

时间复杂度：O(n)，左右指针总共扫一遍数组。

空间复杂度：O(1)，只用了几个变量。

一句话记忆

CAUTION

接雨水就是：左右最高墙决定水位，短板那边先结算，低于最高墙的差值就是水。

买卖股票最佳时机

买卖股票最佳时机是什么？

题目通常是：

给你一个数组 prices，prices[i] 表示第 i 天股票价格。
你只能买一次、卖一次，必须先买后卖。
求最大利润。

例如：

prices = [7, 1, 5, 3, 6, 4]

最佳操作是：

第 1 天价格 1 买入
第 4 天价格 6 卖出
最大利润 = 6 - 1 = 5

核心思路

从左到右扫描价格。

维护两个变量：

minPrice：到今天为止见过的最低价格。

maxProfit：到今天为止能得到的最大利润。

每天都假设“今天卖出”，利润就是：

prices[i] - minPrice

然后更新最大利润。

C# 代码

using System; // 引入 System 命名空间，用来使用 Math.Min 和 Math.Max

public class Solution // 定义题解类
{ // 类开始
    public int MaxProfit(int[] prices) // 定义求最大利润的方法，输入每天价格数组
    { // 方法开始
        int minPrice = prices[0]; // 记录目前见过的最低买入价格

        int maxProfit = 0; // 记录目前能获得的最大利润，初始为 0

        for (int i = 1; i < prices.Length; i++) // 从第二天开始遍历价格
        { // for 开始
            int profit = prices[i] - minPrice; // 假设今天卖出，计算利润

            maxProfit = Math.Max(maxProfit, profit); // 更新最大利润

            minPrice = Math.Min(minPrice, prices[i]); // 更新目前见过的最低价格
        } // for 结束

        return maxProfit; // 返回最大利润
    } // 方法结束
} // 类结束

为什么这样是对的？

因为卖出必须发生在买入之后。

当你扫描到第 i 天时，minPrice 一定是第 i 天之前或当天见过的最低价格。

所以：

prices[i] - minPrice

就是“如果今天卖出，最多能赚多少”。

每一天都试一次卖出，就能找到最大利润。

复杂度

时间复杂度：O(n)，只遍历一次数组。

空间复杂度：O(1)，只用了两个变量。

一句话记忆

NOTE

买卖股票最佳时机就是：一路记录历史最低买入价，每天都尝试卖出并更新最大利润。

下一个排列

下一个排列是什么？

题目通常是：

给你一个整数数组 nums，把它变成字典序中“刚好比当前排列大”的下一个排列。
如果当前已经是最大排列，就变成最小排列。
要求原地修改。

比如：

[1, 2, 3] -> [1, 3, 2]
[3, 2, 1] -> [1, 2, 3]
[1, 3, 5, 4, 2] -> [1, 4, 2, 3, 5]

核心思路

从右往左找第一个：

nums[i] < nums[i + 1]

这个 i 叫 pivot，也就是“可以变大的位置”。

然后从右往左找第一个比 nums[i] 大的数，和它交换。

最后把 i + 1 到末尾的后缀反转。

为什么要反转后缀？

因为从右往左找 pivot 时，pivot 右边一定是降序的。

交换后，为了让结果“刚好变大一点点”，后缀必须变成最小顺序，也就是升序。

降序后缀反转后正好变升序。

C# 代码

public class Solution // 定义题解类
{ // 类开始
    public void NextPermutation(int[] nums) // 定义下一个排列方法，直接修改原数组
    { // 方法开始
        int i = nums.Length - 2; // 从倒数第二个位置开始找 pivot

        while (i >= 0 && nums[i] >= nums[i + 1]) // 从右往左找第一个 nums[i] 小于右边元素的位置
        { // while 开始
            i--; // 当前不满足条件，继续往左找
        } // while 结束

        if (i >= 0) // 如果找到了 pivot，说明当前不是最大排列
        { // if 开始
            int j = nums.Length - 1; // 从最右边开始找比 nums[i] 大的数

            while (j > i && nums[j] <= nums[i]) // 找到第一个大于 nums[i] 的元素
            { // while 开始
                j--; // 当前元素不够大，继续往左找
            } // while 结束

            Swap(nums, i, j); // 交换 pivot 和右侧刚好更大的元素
        } // if 结束

        Reverse(nums, i + 1, nums.Length - 1); // 反转 pivot 后面的后缀，让后缀变成最小升序
    } // 方法结束

    private void Swap(int[] nums, int left, int right) // 定义交换数组两个位置的方法
    { // 方法开始
        int temp = nums[left]; // 临时保存左边元素

        nums[left] = nums[right]; // 把右边元素放到左边位置

        nums[right] = temp; // 把原来的左边元素放到右边位置
    } // 方法结束

    private void Reverse(int[] nums, int left, int right) // 定义反转数组一段区间的方法
    { // 方法开始
        while (left < right) // 当左右指针还没有相遇时继续交换
        { // while 开始
            Swap(nums, left, right); // 交换左右指针对应的元素

            left++; // 左指针向右移动

            right--; // 右指针向左移动
        } // while 结束
    } // 方法结束
} // 类结束

复杂度

时间复杂度：O(n)，最多从右到左扫几遍数组。

空间复杂度：O(1)，原地修改，只用了几个变量。

一句话记忆

TIP

下一个排列就是：从右找下降点，换成右边刚好更大的数，再反转后缀变成最小。

缺失的第一个正数

缺失的第一个正数是什么？

题目通常是：

给你一个未排序的整数数组 nums，找出其中没有出现的最小正整数。
要求时间复杂度 O(n)，空间复杂度 O(1)。

例如：

nums = [3, 4, -1, 1]

缺失的第一个正数是：

2

核心思路

数组长度是 n。

缺失的第一个正数只可能在：

1 到 n + 1

所以我们只关心 [1, n] 范围内的数字。

关键想法是：

数字 1 应该放到 index 0
数字 2 应该放到 index 1
数字 3 应该放到 index 2
数字 x 应该放到 index x - 1

把能放回正确位置的数字都放回去。

最后从左到右扫描：

如果 nums[i] != i + 1
那么 i + 1 就是缺失的第一个正数

C# 代码

public class Solution // 定义题解类
{ // 类开始
    public int FirstMissingPositive(int[] nums) // 定义寻找缺失的第一个正数方法
    { // 方法开始
        int n = nums.Length; // 记录数组长度

        for (int i = 0; i < n; i++) // 遍历数组，尝试把每个数字放到它应该在的位置
        { // for 开始
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) // 当前数字在有效范围内，并且目标位置还不是它自己
            { // while 开始
                int targetIndex = nums[i] - 1; // 计算当前数字应该去的目标下标

                Swap(nums, i, targetIndex); // 把当前数字交换到它应该在的位置
            } // while 结束
        } // for 结束

        for (int i = 0; i < n; i++) // 再次从左到右扫描数组
        { // for 开始
            if (nums[i] != i + 1) // 如果当前位置没有放着应该出现的数字
            { // if 开始
                return i + 1; // 返回这个位置对应的正整数
            } // if 结束
        } // for 结束

        return n + 1; // 如果 1 到 n 都存在，那么缺失的第一个正数就是 n + 1
    } // 方法结束

    private void Swap(int[] nums, int left, int right) // 定义交换数组两个位置的方法
    { // 方法开始
        int temp = nums[left]; // 临时保存左边位置的值

        nums[left] = nums[right]; // 把右边位置的值放到左边

        nums[right] = temp; // 把原来的左边值放到右边
    } // 方法结束
} // 类结束

为什么 while 不是 if？

因为一次交换后，新的 nums[i] 可能仍然是一个需要归位的数字。

比如：

nums[i] = 3

交换后当前位置可能又变成：

nums[i] = 1

那 1 也应该继续放到 index 0。

所以这里要用 while，一直放到当前位置不能再放为止。

复杂度

时间复杂度：O(n)，虽然有 while，但每个数字最多被交换到正确位置一次。

空间复杂度：O(1)，原地交换，没有使用额外数组。

一句话记忆

IMPORTANT

缺失的第一个正数就是：数字 x 放到下标 x - 1，整理后第一个位置不对的下标，就是答案。

矩阵置零

矩阵置零

如果矩阵里某个位置是 0，就把它所在的整行、整列都变成 0。

核心思路

不能一边遍历一边直接把行列置零，因为新置出来的 0 会污染后续判断。

正确做法是：

先记录第一行、第一列原本是否有 0。 然后用第一行、第一列当“标记数组”。 最后根据标记，把内部格子置零。 最后再单独处理第一行、第一列。

public class Solution // 定义题解类
{ // 类开始
    public void SetZeroes(int[][] matrix) // 定义矩阵置零方法，直接修改原矩阵
    { // 方法开始
        int rows = matrix.Length; // 获取矩阵的行数
        int cols = matrix[0].Length; // 获取矩阵的列数

        bool firstRowZero = false; // 记录第一行原本是否有 0
        bool firstColZero = false; // 记录第一列原本是否有 0

        for (int col = 0; col < cols; col++) // 遍历第一行
        { // 循环开始
            if (matrix[0][col] == 0) // 如果第一行中发现 0
            { // 条件开始
                firstRowZero = true; // 标记第一行最后需要全部置零
                break; // 已经确定第一行要置零，可以停止检查
            } // 条件结束
        } // 循环结束

        for (int row = 0; row < rows; row++) // 遍历第一列
        { // 循环开始
            if (matrix[row][0] == 0) // 如果第一列中发现 0
            { // 条件开始
                firstColZero = true; // 标记第一列最后需要全部置零
                break; // 已经确定第一列要置零，可以停止检查
            } // 条件结束
        } // 循环结束

        for (int row = 1; row < rows; row++) // 从第二行开始遍历内部区域
        { // 外层循环开始
            for (int col = 1; col < cols; col++) // 从第二列开始遍历内部区域
            { // 内层循环开始
                if (matrix[row][col] == 0) // 如果当前格子原本是 0
                { // 条件开始
                    matrix[row][0] = 0; // 用第一列标记当前行需要置零
                    matrix[0][col] = 0; // 用第一行标记当前列需要置零
                } // 条件结束
            } // 内层循环结束
        } // 外层循环结束

        for (int row = 1; row < rows; row++) // 再次遍历内部区域
        { // 外层循环开始
            for (int col = 1; col < cols; col++) // 检查每一个内部格子
            { // 内层循环开始
                if (matrix[row][0] == 0 || matrix[0][col] == 0) // 如果当前行或当前列被标记为 0
                { // 条件开始
                    matrix[row][col] = 0; // 把当前格子置为 0
                } // 条件结束
            } // 内层循环结束
        } // 外层循环结束

        if (firstRowZero) // 如果第一行原本有 0
        { // 条件开始
            for (int col = 0; col < cols; col++) // 遍历第一行所有列
            { // 循环开始
                matrix[0][col] = 0; // 把第一行当前位置置为 0
            } // 循环结束
        } // 条件结束

        if (firstColZero) // 如果第一列原本有 0
        { // 条件开始
            for (int row = 0; row < rows; row++) // 遍历第一列所有行
            { // 循环开始
                matrix[row][0] = 0; // 把第一列当前位置置为 0
            } // 循环结束
        } // 条件结束
    } // 方法结束
} // 类结束

复杂度

时间复杂度：O(m * n)，每个格子最多检查几次。 空间复杂度：O(1)，没有额外开数组，只用了两个布尔变量。

面试记忆

WARNING

先保存首行首列，再用首行首列做标记；内部置零后，最后处理首行首列。

螺旋矩阵

螺旋矩阵

按“右、下、左、上”的顺序读矩阵，每走完一条边，就把这条边往里面缩一层。

核心思路

维护四个边界：

top：当前最上面一行 bottom：当前最下面一行 left：当前最左边一列 right：当前最右边一列

每一轮按顺序遍历：

右：top 行，从 left 到 right 下：right 列，从 top + 1 到 bottom 左：bottom 行，从 right - 1 到 left 上：left 列，从 bottom - 1 到 top

using System.Collections.Generic; // 引入 List 和 IList 所在的命名空间

public class Solution // 定义题解类
{ // 类开始
    public IList<int> SpiralOrder(int[][] matrix) // 定义螺旋遍历方法，返回遍历结果
    { // 方法开始
        List<int> result = new List<int>(); // 创建结果列表，用来保存螺旋顺序的数字

        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) // 如果矩阵为空，直接返回空结果
        { // 条件开始
            return result; // 返回空列表
        } // 条件结束

        int top = 0; // 定义上边界，初始为第一行
        int bottom = matrix.Length - 1; // 定义下边界，初始为最后一行
        int left = 0; // 定义左边界，初始为第一列
        int right = matrix[0].Length - 1; // 定义右边界，初始为最后一列

        while (top <= bottom && left <= right) // 只要边界还没有交叉，就继续螺旋遍历
        { // while 开始
            for (int col = left; col <= right; col++) // 从左到右遍历当前上边界这一行
            { // for 开始
                result.Add(matrix[top][col]); // 把当前格子加入结果
            } // for 结束

            top++; // 上边界向下收缩一行

            for (int row = top; row <= bottom; row++) // 从上到下遍历当前右边界这一列
            { // for 开始
                result.Add(matrix[row][right]); // 把当前格子加入结果
            } // for 结束

            right--; // 右边界向左收缩一列

            if (top <= bottom) // 如果收缩后仍然还有行，才可以从右到左遍历
            { // 条件开始
                for (int col = right; col >= left; col--) // 从右到左遍历当前下边界这一行
                { // for 开始
                    result.Add(matrix[bottom][col]); // 把当前格子加入结果
                } // for 结束

                bottom--; // 下边界向上收缩一行
            } // 条件结束

            if (left <= right) // 如果收缩后仍然还有列，才可以从下到上遍历
            { // 条件开始
                for (int row = bottom; row >= top; row--) // 从下到上遍历当前左边界这一列
                { // for 开始
                    result.Add(matrix[row][left]); // 把当前格子加入结果
                } // for 结束

                left++; // 左边界向右收缩一列
            } // 条件结束
        } // while 结束

        return result; // 返回螺旋遍历结果
    } // 方法结束
} // 类结束

复杂度

时间复杂度：O(m * n)，每个元素只访问一次。 空间复杂度：O(1)，不算返回结果的话，只用了四个边界变量。

面试记忆

右、下、左、上四个方向轮流走；每走完一条边，就收缩对应边界。