1503. Last Moment Before All Ants Fall Out of a Plank¶
题目信息¶
- 题号:
1503
- 难度:
Medium
- 主题:
数组、运动模拟、等价变换、贪心
- 原题:
- 重点:
从逐时刻模拟碰撞,推导到忽略身份后的轨迹穿越,再在线聚合最晚掉落时刻
题目重述¶
长度为 n 的木板覆盖坐标区间 [0,n]。木板上有若干只蚂蚁,每只蚂蚁每秒移动一个单位:
left保存初始向左移动的蚂蚁位置;right保存初始向右移动的蚂蚁位置。
所有初始位置互不相同。两只相向而行的蚂蚁相遇时,会立即同时反向,反向不消耗时间。蚂蚁到达坐标
0 或 n 时立即掉下木板。
返回最后一只蚂蚁掉下木板的时刻。位于 0 且向左移动,或位于 n 且向右移动的蚂蚁,会在
时刻 0 掉落。
约束为 1 <= n <= 10^4,所有位置位于 [0,n],并且木板上至少有一只蚂蚁。
自建示例¶
输入:n = 4, left = [4,3], right = [0,1]
输出:4
忽略身份后,位置 4 的向左轨迹需要 4 秒到达左端,位置 0 的向右轨迹需要 4 秒到达右端。
输入:n = 7, left = [5], right = [2]
输出:5
向左蚂蚁的掉落时间为 5,向右蚂蚁的掉落时间为 7 - 2 = 5。
输入:n = 5, left = [0], right = [5]
输出:0
两只蚂蚁都位于各自移动方向的端点,立即掉落。
C++ 实现¶
#include <algorithm>
#include <unordered_map>
#include <vector>
class Solution {
private:
struct Ant {
int position2;
int direction;
bool alive;
};
int simulateHalfSteps(
int n,
const std::vector<int>& left,
const std::vector<int>& right
) {
std::vector<Ant> ants;
ants.reserve(left.size() + right.size());
for (int position : left) {
ants.push_back({position * 2, -1, true});
}
for (int position : right) {
ants.push_back({position * 2, 1, true});
}
const int end2 = n * 2;
int aliveCount = static_cast<int>(ants.size());
int elapsedHalfSteps = 0;
for (Ant& ant : ants) {
const bool fallsImmediately =
(ant.position2 == 0 && ant.direction == -1) ||
(ant.position2 == end2 && ant.direction == 1);
if (fallsImmediately) {
ant.alive = false;
--aliveCount;
}
}
while (aliveCount > 0) {
++elapsedHalfSteps;
for (Ant& ant : ants) {
if (ant.alive) {
ant.position2 += ant.direction;
}
}
for (Ant& ant : ants) {
if (!ant.alive) continue;
if (ant.position2 == 0 || ant.position2 == end2) {
ant.alive = false;
--aliveCount;
}
}
std::unordered_map<int, std::vector<int>> collisionGroups;
for (int index = 0; index < static_cast<int>(ants.size()); ++index) {
if (ants[index].alive) {
collisionGroups[ants[index].position2].push_back(index);
}
}
for (auto& entry : collisionGroups) {
std::vector<int>& indices = entry.second;
if (indices.size() == 2) {
ants[indices[0]].direction *= -1;
ants[indices[1]].direction *= -1;
}
}
}
return elapsedHalfSteps / 2;
}
int collectFallTimes(
int n,
const std::vector<int>& left,
const std::vector<int>& right
) {
std::vector<int> fallTimes;
fallTimes.reserve(left.size() + right.size());
for (int position : left) {
fallTimes.push_back(position);
}
for (int position : right) {
fallTimes.push_back(n - position);
}
return *std::max_element(fallTimes.begin(), fallTimes.end());
}
int aggregateMaximum(
int n,
const std::vector<int>& left,
const std::vector<int>& right
) {
int lastMoment = 0;
for (int position : left) {
lastMoment = std::max(lastMoment, position);
}
for (int position : right) {
lastMoment = std::max(lastMoment, n - position);
}
return lastMoment;
}
public:
int getLastMoment(
int n,
std::vector<int>& left,
std::vector<int>& right
) {
return aggregateMaximum(n, left, right);
}
};
题解¶
逐时刻模拟¶
直接方法按照题意维护每只蚂蚁的位置、方向和存活状态。碰撞可能发生在半秒时刻,因此
simulateHalfSteps 把坐标扩大两倍,并用半秒作为一个离散时间步:
原位置 position -> 2 * position
木板右端 n -> 2 * n
每个半步位移 -> 1
每轮先移动全部存活蚂蚁,再删除到达端点的蚂蚁,最后按位置分组并让相遇的两只蚂蚁同时反向。 这种实现完整保留了物理过程,也能覆盖整数时刻和半整数时刻的碰撞。
身份状态的代价¶
木板长度为 n,所有蚂蚁最迟在 n 秒内掉落,因此模拟至多执行 2n 个半步。每个半步都要扫描
蚂蚁并建立碰撞分组,主要成本来自持续追踪每只蚂蚁的身份。
题目只询问最后掉落时刻,不询问某个身份最终从哪一端离开。删除身份信息后,碰撞可以使用更简单的等价模型。
轨迹穿越等价¶
两只速度相同、方向相反的蚂蚁相遇后同时反向。若保留身份,可以理解为两只蚂蚁分别沿另一条轨迹继续移动; 若忽略身份,则与它们保持原方向直接穿过完全等价。
两个模型在任意时刻拥有相同的位置集合:
真实模型:身份 A 接续身份 B 的出射轨迹,身份 B 接续身份 A 的出射轨迹
穿越模型:两条轨迹保持方向继续延伸
碰撞只交换了轨迹由哪个身份占据,没有改变轨迹本身。所有到达端点的时刻因此完全相同,最后掉落时刻也不变。
静态掉落时间¶
穿越模型删除了全部碰撞。每条轨迹从初始位置直线移动到对应端点:
向左轨迹 position -> 掉落时间 position
向右轨迹 position -> 掉落时间 n - position
collectFallTimes 计算并保存所有轨迹的掉落时间,再取最大值。每只蚂蚁只处理一次,时间已经降为线性。
在线聚合¶
题目只需要所有掉落时间的最大值,不需要保存完整列表。aggregateMaximum 在计算每个时间后立即更新
lastMoment:
lastMoment = max(lastMoment, 当前轨迹的掉落时间)
扫描结束时,不变量是:lastMoment 等于所有已处理轨迹中的最晚掉落时刻。处理下一条轨迹只需一次最大值
更新,最终得到全部轨迹的最大值,额外空间降为常数。
状态演化¶
对 n = 4, left = [4,3], right = [0,1]:
轨迹 |
掉落时间 |
更新后 |
|---|---|---|
向左,位置 4 |
4 |
4 |
向左,位置 3 |
3 |
4 |
向右,位置 0 |
|
4 |
向右,位置 1 |
|
4 |
真实过程中会发生多次碰撞,但穿越模型中的四条轨迹分别在时刻 3 或 4 到达端点,所以答案为 4。
三种方法的关系¶
半步模拟保留位置、方向、存活状态和碰撞关系;穿越等价删除身份与碰撞,只保留每条轨迹的静态掉落时间; 在线聚合继续删除中间时间数组,只保留当前最大值。
三步优化依次减少状态:
动态物理状态 -> 独立轨迹时间 -> 一个最大值
公开入口调用 aggregateMaximum,因为它直接表达题目真正需要的统计量。
边界处理¶
left 为空时只扫描向右轨迹,right 为空时只扫描向左轨迹。题目保证至少存在一只蚂蚁,因此主方法
一定会处理至少一个位置。
位置 0 的向左轨迹和位置 n 的向右轨迹贡献时间 0。大量碰撞不会影响结果,因为碰撞只交换身份,不改变
轨迹集合。任意掉落时间都位于 [0,n],使用 int 足够。
复杂度分析¶
设蚂蚁总数为 k。半步模拟最多执行 2n 轮,每轮扫描并分组全部蚂蚁,平均时间为 O(nk),
额外空间为 O(k)。
保存掉落时间的方法访问每只蚂蚁一次,时间为 O(k),数组占用 O(k) 空间。主方法同样为
O(k) 时间,只维护当前最大值,额外空间为 O(1)。