Medium

题目描述

有一块长度为 n 单位的木板。一些蚂蚁在木板上行走，每只蚂蚁以每秒 1 单位的速度移动。有些蚂蚁向左移动，有些向右移动。

当两只朝不同方向移动的蚂蚁在某一点相遇时，它们会改变方向并继续移动。假设改变方向不需要额外的时间。

当蚂蚁在时间 t 到达木板的一端时，它会立即掉下木板。

给你一个整数 n 和两个整数数组 left 和 right，分别表示向左和向右移动的蚂蚁的位置，返回最后一只蚂蚁从木板上掉下来的时刻。

示例 1:

输入: n = 4, left = [4,3], right = [0,1]
输出: 4
解释: 最后一只蚂蚁在 t = 4 秒时从木板上掉下来。

示例 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⁴
  • 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 中的所有值都是唯一的，每个值只能出现在两个数组中的一个里。

解题思路

这道题的关键洞察是：当两只蚂蚁相遇并改变方向时，从全局角度看，可以认为它们穿过了彼此而没有改变方向。

核心思路

蚂蚁碰撞改变方向的过程，本质上等价于蚂蚁直接穿过彼此继续原方向移动。这是因为：

  • 碰撞前后，蚂蚁的总体运动状态保持不变
  • 我们只关心最后掉落的时间，而不关心具体是哪只蚂蚁

基于这个理解，问题简化为：

  1. 向左移动的蚂蚁：需要 position 秒到达左端（位置0）
  2. 向右移动的蚂蚁：需要 n - position 秒到达右端（位置n）

解法分析

方法一：直接计算法（推荐）

  • 遍历所有蚂蚁，计算每只蚂蚁到达边界的时间
  • 返回所有时间中的最大值

方法二：数学优化法

  • 向左蚂蚁的最大掉落时间 = max(left)
  • 向右蚂蚁的最大掉落时间 = n - min(right)
  • 答案为两者的最大值

两种方法本质相同，第二种方法利用了数学性质，代码更简洁。

代码实现

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int maxTime = 0;
        
        // 向左移动的蚂蚁：需要 position 秒到达左端
        for (int pos : left) {
            maxTime = max(maxTime, pos);
        }
        
        // 向右移动的蚂蚁：需要 (n - position) 秒到达右端
        for (int pos : right) {
            maxTime = max(maxTime, n - pos);
        }
        
        return maxTime;
    }
};

class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        max_time = 0
        
        # 向左移动的蚂蚁：需要 position 秒到达左端
        for pos in left:
            max_time = max(max_time, pos)
        
        # 向右移动的蚂蚁：需要 (n - position) 秒到达右端
        for pos in right:
            max_time = max(max_time, n - pos)
        
        return max_time

public class Solution {
    public int GetLastMoment(int n, int[] left, int[] right) {
        int maxTime = 0;
        
        // 向左移动的蚂蚁：需要 position 秒到达左端
        foreach (int pos in left) {
            maxTime = Math.Max(maxTime, pos);
        }
        
        // 向右移动的蚂蚁：需要 (n - position) 秒到达右端
        foreach (int pos in right) {
            maxTime = Math.Max(maxTime, n - pos);
        }
        
        return maxTime;
    }
}

/**
 * @param {number} n
 * @param {number[]} left
 * @param {number[]} right
 * @return {number}
 */
var getLastMoment = function(n, left, right) {
    let maxTime = 0;
    
    // 向左移动的蚂蚁：需要 position 秒到达左端
    for (let pos of left) {
        maxTime = Math.max(maxTime, pos);
    }
    
    // 向右移动的蚂蚁：需要 (n - position) 秒到达右端
    for (let pos of right) {
        maxTime = Math.max(maxTime, n - pos);
    }
    
    return maxTime;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(L + R)L 和 R 分别为 left 和 right 数组的长度
空间复杂度O(1)只使用常数额外空间

相关题目