题目描述
给你一个下标从 0 开始的整数数组 stones
,数组中的元素 严格递增,表示一条河中石头的位置。
一只青蛙一开始在第一块石头上,它想到达最后一块石头,然后回到第一块石头。同时每块石头 至多 到达 一次。
一次跳跃的 长度 是青蛙跳跃前和跳跃后所在两块石头之间的距离。
- 更正式的,如果青蛙从
stones[i]
跳到stones[j]
,跳跃的长度为|stones[i] - stones[j]|
。
一条路径的 代价 是这条路径里的 最大跳跃长度。
请你返回这只青蛙的 最小代价。
样例
输入:stones = [0,2,5,6,7]
输出:5
解释:上图展示了一条最优路径。
这条路径的代价是 5,是这条路径中的最大跳跃长度。
无法得到一条代价小于 5 的路径,我们返回 5。
输入:stones = [0,3,9]
输出:9
解释:
青蛙可以直接跳到最后一块石头,然后跳回第一块石头。
在这条路径中,每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9。
这是可行路径中的最小代价。
限制
2 <= stones.length <= 10^5
0 <= stones[i] <= 10^9
stones[0] == 0
stones
中的元素严格递增。
算法1
(二分答案,贪心) $O(n \log S)$
- 最大代价最小,可以考虑二分答案。
- 假设当前二分的最大代价为 $m$,判定在这个代价下是否可以满足条件。
- 贪心地看,正向的过程在限制最大代价的情况下,尽可能地挑选间隔最大的路径跳跃到达终点,然后判定没有经过的石子是否也满足条件。
时间复杂度
- 假设二分的上限为 $S$,每次判定仅需要 $O(n)$ 的时间,故总时间复杂度为 $O(n \log S)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储判定过程的临时数组。
C++ 代码
class Solution {
private:
bool check(int m, const vector<int> &stones) {
const int n = stones.size();
vector<bool> mark(n, false);
// 第一次遍历,将最大间隔路径上的石子标记
for (int i = 0, j = 1; j < n; i = j - 1, mark[j - 1] = true) {
// 找到下一个大于当前间隔的位置 j
while (j < n && stones[j] - stones[i] <= m)
j++;
// 如果 j 就是 i 的下一个位置,则不满足
if (i == j - 1)
return false;
}
// 最后一个位置标记清空
mark[n - 1] = false;
for (int i = 0, j = 1; j < n; i = j++) {
// 找到 i 下一个没被标记的位置
while (j < n && mark[j])
j++;
// 如果下一个没被标记的位置和当前距离差距大于 m,则不满足
if (stones[j] - stones[i] > m)
return false;
}
return true;
}
public:
int maxJump(vector<int>& stones) {
int l = 1, r = stones.back();
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid, stones)) r = mid;
else l = mid + 1;
}
return l;
}
};
算法2
(贪心) $O(n)$
- 考虑将问题转为两只青蛙同时从起点开始,期间不能跳到相同的位置上。
- 一种贪心方案是两只间隔地进行跳跃,保证中途不会跳到相同的位置上。可以通过反证法证明这个方案的最优性,假如中途某一只青蛙跨越了两个或更多的石子跳跃,则另一只青蛙根据贪心必定跳跃到了被越过的石子上,则不如让跨越的青蛙只跨越一个石子,这样会降低这个局部下的最大代价,即 $a, b, c, d$ 四个石子,如果一只青蛙从 $a$ 跳到了 $d$,则不如让其从 $a$ 跳到 $c$,另一只从 $b$ 跳到 $d$,都会不差于之前的情况。
时间复杂度
- 遍历数组一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int maxJump(vector<int>& stones) {
const int n = stones.size();
if (n == 2)
return stones[1] - stones[0];
int ans = 0;
for (int i = 2; i < n; i++)
ans = max(ans, stones[i] - stones[i - 2]);
return ans;
}
};