---

1503. 所有蚂蚁掉下来前的最后一刻

• 标签：脑筋急转弯、数组、模拟
• 难度：中等

题目链接

• 1503. 所有蚂蚁掉下来前的最后一刻 - 力扣

题目大意

描述：有一块长度为 $n$ 的木板上，$n+1$ 个位置标记为 $0, 1, \dots, n$。给定两个数组 $left$ 和 $right$，表示蚂蚁的初始位置。$left$ 中的蚂蚁向左移动，$right$ 中的蚂蚁向右移动。所有蚂蚁同时以每秒 $1$ 单位的速度移动。当两只蚂蚁相遇时，它们会立即掉头。

要求：返回所有蚂蚁都从木板上掉下去的最后时刻。

说明：

• $1 \le n \le 10^4$。
• $0 \le left.length, right.length \le n + 1$。
• 所有蚂蚁位置保证不重叠。

示例：

• 示例 1：

输入：n = 4, left = [4,3], right = [0,1]
输出：4
解释：如上图所示：
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。

• 示例 2：

输入：n = 7, left = [], right = [0,1,2,3,4,5,6,7]
输出：7
解释：所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。

解题思路

思路 1：脑筋急转弯

1. 核心思想

蚂蚁相遇掉头这一行为，从蚂蚁身份的角度看是掉头了，但从整体效果看，相当于两只蚂蚁互相穿过对方继续前进（因为蚂蚁没有区别）。

因此，等效于：所有蚂蚁都不掉头，直接按照原方向走到木板尽头。

那么每只蚂蚁掉下去的时间就是：

• 向左的蚂蚁：位置 $pos$。
• 向右的蚂蚁：$n - pos$。

最终时间 = 所有蚂蚁中最大的掉落时间。

2. 具体步骤

第 1 步：初始化 $ans = 0$。

第 2 步：对于 $left$ 中的每个位置 $pos$：$ans = max(ans, pos)$。

第 3 步：对于 $right$ 中的每个位置 $pos$：$ans = max(ans, n - pos)$。

第 4 步：返回 $ans$。

3. 正确性证明

• 两只蚂蚁相遇后掉头，和它们互相穿过继续走，在"什么时间什么位置有蚂蚁"这个宏观层面上是完全等价的。
• 因为蚂蚁不可区分，掉头相当于交换了两只蚂蚁的身份。从"蚂蚁分布"的视角看，效果就是直接穿过。
• 所以每只蚂蚁掉下去的时间就是它朝当前方向走到尽头的时间。

4. 举例说明

以 $n = 4, left = [4, 3], right = [0, 1]$ 为例：

位置: 0---1---2---3---4
      →   →       ←   ←

蚂蚁掉头等效：

• 左蚂蚁在 $4$：向左走 $4$ 秒掉下。
• 左蚂蚁在 $3$：向左走 $3$ 秒掉下。
• 右蚂蚁在 $0$：向右走 $4$ 秒掉下。
• 右蚂蚁在 $1$：向右走 $3$ 秒掉下。

最大时间 $= max(4, 3, 4, 3) = 4$ 秒。

以 $n = 7, left = [], right = [0, 1, 2, 3, 4, 5, 6, 7]$ 为例：

所有蚂蚁向右：

• $pos=0$：$7$ 秒，$pos=1$：$6$ 秒，$\dots$，$pos=7$：$0$ 秒。
• 最大时间 $= 7$ 秒。

思路 1：代码

class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        ans = 0
        for pos in left:
            ans = max(ans, pos)
        for pos in right:
            ans = max(ans, n - pos)
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。