本文涉及知识点

贪心 优化后不需要二分

LeetCode2498. 青蛙过河 II

给你一个下标从 0 开始的整数数组 stones ，数组中的元素 严格递增 ，表示一条河中石头的位置。青蛙一开始在第一块石头上，它想到达最后一块石头，然后回到第一块石头。同时每块石头 至多 到达 一次。

一次跳跃的 长度 是青蛙跳跃前和跳跃后所在两块石头之间的距离。

更正式的，如果青蛙从 stones[i] 跳到 stones[j] ，跳跃的长度为 |stones[i] - stones[j]| 。一条路径的 代价 是这条路径里的 最大跳跃长度 。

请你返回这只青蛙的 最小代价 。

示例 1：

输入：stones = [0,2,5,6,7]

输出：5

解释：上图展示了一条最优路径。

这条路径的代价是 5 ，是这条路径中的最大跳跃长度。

无法得到一条代价小于 5 的路径，我们返回 5 。

示例 2：

输入：stones = [0,3,9]

输出：9

解释：

青蛙可以直接跳到最后一块石头，然后跳回第一块石头。

在这条路径中，每次跳跃长度都是 9 。所以路径代价是 max(9, 9) = 9 。

这是可行路径中的最小代价。

提示：

2 <= stones.length <= 10⁵

0 <= stones[i] <= 10⁹

stones[0] == 0

stones 中的元素严格递增。

贪心

n = stones.length

性质一：一定存在最优解，所有石头都跳。用决策包容性证明：

假定某最优解，第i块石头没有通过。去程其前面的石头是i1，后面的石头是i2。则将

i

1

→

i

2

转成

i

1

→

i

→

i

2

i1 \rightarrow i2 转成i1 \rightarrow i \rightarrow i2

i1→i2转成i1→i→i2仍然是最优解。

性质二：一定存在最优解，除起点和终点外，去程（返程）不经过任意两个连续石头。用决策包容性证明：

不失一般性，假定去程经过：

1

→

2

→

4

返程经过

0

→

3

→

5

1 \rightarrow 2 \rightarrow 4 返程经过0 \rightarrow 3 \rightarrow 5

1→2→4返程经过0→3→5

改成

0

→

2

→

4

返程经过

1

→

3

→

5

0 \rightarrow 2 \rightarrow 4 返程经过1 \rightarrow 3 \rightarrow 5

0→2→4返程经过1→3→5也是最优解。

修改前：0能够到达3，说明0能到达2,1也能到达3。

性质三：如果石头超过3个。则一定存在最优解，第2个石头是去程。如果不是，去程和返程经过的石头互换。

同时符合上面三个的性质的最优解：

去程：0 2 4…n-1 返程 n-1 …5 3 1 0

去程枚举起点：如果 i 是 n-1 ，则不跳。 如果 i+2 < n 则跳到 i+2；否则跳到i+1。 除终点外，枚举所有偶数。

返程枚举终点：如果i 是 n-1,不会是终点。如果i+2 < n，则起点是n+2；否则起点是i+1。 除终点外，枚举所有奇数和0。

两者综合：枚举终点外所有的点。

代码

核心代码

<code>class Solution { -- -->

public:

int maxJump(vector<int>& stones) {

int ret = 0;

for (int i = 0; i + 1 < stones.size(); i++) {

ret = max(ret, stones[i + 1] - stones[i]);

if (i + 2 < stones.size()) {

ret = max(ret, stones[i + 2] - stones[i]);

}

}

return ret;

}

};

测试

vector<int> stones;

TEST_METHOD(TestMethod13)

{

stones = { 0, 2, 5, 6, 7 };

auto res = Solution().maxJump(stones);

AssertEx(5, res);

}

TEST_METHOD(TestMethod14)

{

stones = { 0,3,9 };

auto res = Solution().maxJump(stones);

AssertEx(9, res);

}

TEST_METHOD(TestMethod15)

{

stones = { 1,2 };

auto res = Solution().maxJump(stones);

AssertEx(1, res);

}

};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。