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

题目描述

这是 LeetCode 上的 1503. 所有蚂蚁掉下来前的最后一刻 ，难度为 中等。

有一块木板，长度为 n 个单位。

一些蚂蚁在木板上移动，每只蚂蚁都以每秒一个单位的速度移动。

其中，一部分蚂蚁向左移动，其他蚂蚁向右移动。

当两只向不同方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。

假设更改方向不会花费任何额外时间。

而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。

给你一个整数 n 和两个整数数组 left 以及 right，两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。

请你返回最后一只蚂蚁从木板上掉下来的时刻。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, left = [4,3], right = [0,1]

输出：4

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

示例 2：

1
2
3
4
5
输入：n = 7, left = [], right = [0,1,2,3,4,5,6,7]

输出：7

解释：所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。

示例 3：

1
2
3
4
5
输入：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 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。

模拟

当一只蚂蚁起始位置为 x，方向往左，且往左移动过程不受其他影响时，其到达左边界所需时间为 x；若方向往右，且往右移动过程不受其他影响时，其到达右边界所需时间为 n - x。

蚂蚁之间的相互影响实际上并不会影响它们到达木板边缘的时间。

两只相遇的蚂蚁只是简单地交换了彼此的移动方向，并没有影响到它们的移动步数，即两只蚂蚁相遇可视为身份互换。

因此，我们只需要分别计算每只蚂蚁单独掉落到木板边缘所需的时间，然后取最大值即可得到所有蚂蚁掉落的最后时刻。

Java 代码：

1
2
3
4
5
6
7
8
class Solution {
    public int getLastMoment(int n, int[] left, int[] right) {
        int ans = 0;
        for (int x : left) ans = Math.max(ans, x);
        for (int x : right) ans = Math.max(ans, n - x);
        return ans;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int ans = 0;
        for (int x : left) ans = max(ans, x);
        for (int x : right) ans = max(ans, n - x);
        return ans;
    }
};

Python 代码：
1
2
3
class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        return max(left + [n - x for x in right])

TypeScript 代码：
1
2
3
4
5
6
function getLastMoment(n: number, left: number[], right: number[]): number {
    let ans = 0;
    for (const x of left) ans = Math.max(ans, x);
    for (const x of right) ans = Math.max(ans, n - x);
    return ans;
};

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

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1503 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。