LeetCode 题解工作台
所有蚂蚁掉下来前的最后一刻
有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。 当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。 而当蚂蚁在某一时刻 t 到达木板…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·结合·brainteaser
答案摘要
题目关键点在于两只蚂蚁相遇，然后分别调转方向的情况，实际上相当于两只蚂蚁继续往原来的方向移动。因此，我们只需要求出所有蚂蚁中最远的那只蚂蚁的移动距离即可。 注意 和 数组的长度可能为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·brainteaser 题型思路
题目描述
有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。
当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。
而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。
给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。
示例 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 秒才能从木板上掉落。
示例 3：
输入：n = 7, left = [0,1,2,3,4,5,6,7], right = [] 输出：7 解释：所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。
提示：
1 <= n <= 10^40 <= left.length <= n + 10 <= left[i] <= n0 <= right.length <= n + 10 <= right[i] <= n1 <= left.length + right.length <= n + 1left和right中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。
解题思路
方法一：脑筋急转弯
题目关键点在于两只蚂蚁相遇，然后分别调转方向的情况，实际上相当于两只蚂蚁继续往原来的方向移动。因此，我们只需要求出所有蚂蚁中最远的那只蚂蚁的移动距离即可。
注意 和 数组的长度可能为 。
时间复杂度 ，其中 为木板的长度。空间复杂度 。
class Solution:
def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
ans = 0
for x in left:
ans = max(ans, x)
for x in right:
ans = max(ans, n - x)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n + m) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates an understanding of array manipulation and problem-solving techniques.
- question_mark
The candidate can identify key optimizations like ignoring the ant direction swap.
- question_mark
The candidate efficiently determines the maximum time by focusing on edge cases.
常见陷阱
外企场景- error
Mistaking the direction swap as needing a complex simulation instead of a simple time calculation.
- error
Not handling the case where there are no ants in either the `left` or `right` arrays.
- error
Misunderstanding the problem as a simulation of movement, rather than focusing on maximum times.
进阶变体
外企场景- arrow_right_alt
The problem can be extended to consider more complicated interactions, such as different speeds for the ants.
- arrow_right_alt
A variation could involve multiple planks with ants walking between them, requiring a more complex simulation.
- arrow_right_alt
The problem can be modified to track not just the last moment, but also the number of ants left at different moments.