Skip to main content

5453. 所有蚂蚁掉下来前的最后一刻 [medium]

5453. 所有蚂蚁掉下来前的最后一刻 [medium]​

https://leetcode-cn.com/problems/last-moment-before-all-ants-fall-out-of-a-plank/

有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。

当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。

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

给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。

示例 1：

image

输入：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
  • left 和 right 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。

通过次数3,050 | 提交次数6,889

First Try​

2020-07-05

参加的第一场双周赛，首先看到这道题觉得有点乱跳过去了，后来再做以为用模拟暴力写法，结果感觉边界条件太多，还是没写出来。看了题解，竟然是道脑筋急转弯的题目，被虐得一点脾气都没有。

如果不使用抖机灵的写法，不知道怎么写个思路清晰的暴力模拟法。

其实最迷惑的是第一幅图中T1到T2的时候，A和D都没有挪动位置，仅仅是改变了方向。问题是题目中又说改变方向不需要时间，这就有点混乱了。只是最后按照穿越的思路来模拟，发现确实可行，才确认可行。

class Solution(object):
    def getLastMoment(self, n, left, right):
        """
        :type n: int
        :type left: List[int]
        :type right: List[int]
        :rtype: int
        """
        left, right = sorted(left), sorted(right)
        maxleft = left[-1] if len(left) > 0 else 0
        maxright = n - right[0] if len(right) > 0 else 0
        return max(maxleft, maxright)
  • 执行用时：44 ms, 在所有 Python 提交中击败了100.00%的用户
  • 内存消耗：13 MB, 在所有 Python 提交中击败了100.00%的用户
  • failed version

没想出来的模拟版本

class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        total = [[] for i in range(n)]
        
        for ls in left:
            total[ls].append((ls, -1))
        for rs in right:
            total[rs].append((rs, 1))
        # 第一波都不用时间
        # if total[0] < 0:
        #     n -= 1
        # if total[-1] >0:
        #     n -= 1
        while n:
            ne = []
            for e in total:
                curr, nex = e[0], e[0] + e[1]
                total[nex].append([curr, e[1]])