X

LEETCODE 1503. Last Moment Before All Ants Fall Out of a Plank 解题思路分析

题目大意:

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

有一块木板,长度为 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 秒才能从木板上掉落。

示例 4:

输入:n = 9, left = [5], right = [4]
输出:5
解释:t = 1 秒时,两只蚂蚁将回到初始位置,但移动方向与之前相反。

示例 5:

输入:n = 6, left = [6], right = [0]
输出:6

提示:

  • 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
  • leftright 中的所有值都是唯一的,并且每个值 只能出现在二者之一 中。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1503

解题思路分析:

注意要被题目的描述带进沟里,虽然两只蚂蚁相遇后会分别掉头向回走,但向左走与向右走的蚂蚁数量没有改变,只不过在相遇前未走的路程会交给相遇的另一只蚂蚁去完成而已。因此我们实际上可以无视相遇后掉头这个条件,直接理解为左右两队蚂蚁在两个平行的路线上分别前进,求最后一只蚂蚁掉下模板的时间。这样一来问题就变得简单,我们只需要知道当前距离终点最远的蚂蚁所在的位置即可。

实现代码:

public int getLastMoment(int n, int[] left, int[] right) {
    Arrays.sort(left); // 按顺序排列两队蚂蚁的位置
    Arrays.sort(right);
    // 向左走的蚂蚁中距离终点最远的位置
    int minLeft=left.length>0?left[left.length-1]:0;
    // 向右走的蚂蚁中距离终点最远的位置
    int maxRight=right.length>0?n-right[0]:0;
    // 上述两者最大值即为答案
    return Math.max(minLeft,maxRight);
}

本题解法执行时间为8ms。

Runtime: 8 ms, faster than 100.00% of Java online submissions for Last Moment Before All Ants Fall Out of a Plank.

Memory Usage: 52 MB, less than 100.00% of Java online submissions for Last Moment Before All Ants Fall Out of a Plank.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1503-last-moment-before-all-ants-fall-out-of-a-plank-解题思路分析/
Categories: leetcode
kwantong: