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

难度: Medium

有一块木板，长度为 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^4
0 <= left.length <= n + 1
0 <= left[i] <= n
0 <= right.length <= n + 1
0 <= right[i] <= n
1 <= left.length + right.length <= n + 1
left 和 right 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。

Submission

运行时间: 29 ms

内存: 17.0 MB

class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        # size_left = len(left)
        # size_right = len(right)
        # if size_left == size_right:
        #     max_left = max(left)
        #     min_right = min(right)
        #     if max_left > n-min_right:
        #         half = (max_left - min_right) // 2
        #         # return half + n - (min_right + half)
        #         print("a")
        #         return n - min_right
        #     else:
        #         print("b")
        #         # return max_left - min_right + n - min_right
        #         return max_left
        # else:
        #     return n
        # left_max = 0
        # left_max = max(left_max, left)
        # left_max = max(left_max, )
        return max(left + [n-x for x in right])

Explain

在此问题中，蚂蚁改变方向时对最终时间没有影响，因为蚂蚁相遇后改变方向的行为可以视作两只蚂蚁都继续向原来的方向行走。因此，只需要考虑每只蚂蚁到达木板边缘的时间。对于向左移动的蚂蚁，最长时间是它们中最靠右（最大位置）的蚂蚁到达左端的时间。对于向右移动的蚂蚁，最长时间是它们中最靠左（最小位置）的蚂蚁到达右端的时间。这个时间可以通过计算 n 减去该位置得到。最终答案是所有这些时间中的最大值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        # 计算所有向左蚂蚁到达左端的时间，直接使用left中的位置值
        # 计算所有向右蚂蚁到达右端的时间，需要计算n减去每个位置值
        # 时间即为蚂蚁到达木板尽头的时间，取最大值即可
        # 使用列表解析式生成向右蚂蚁到达右端的时间列表
        # 合并两个时间列表，并使用max函数找出最大值返回
        return max(left + [n-x for x in right])

Explore

在这个问题中，我们需要找出所有蚂蚁掉下木板的最长时间。对于向左移动的蚂蚁，它们从其当前位置到达木板左端的时间取决于它们的起始位置。因此，left数组中的最大值表示最右边的蚂蚁到达左端所需时间最长。同理，对于向右移动的蚂蚁，right数组中的最小值表示最左边的蚂蚁到达右端所需时间最长。这两个关键点（left数组中的最大值和right数组中的最小值）决定了所有蚂蚁中最晚掉下木板的时间，因此它们是计算中的关键因素。

是的，可以在一次遍历中同时处理left和right数组。具体方法是在遍历过程中，同时维护left数组的最大值和right数组的最小值。这样可以在一次遍历完成后直接得到两个关键值，从而计算出最终的最长时间。这种方法减少了代码的复杂性并可能提高执行效率，因为它避免了额外的列表操作和多次遍历。