青蛙过河 II

开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第21天，点击查看活动详情

问题描述

给你一个下标从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^5
• 0 <= stones[i] <= 10^9
• stones[0] == 0
• stones中的元素严格递增。

思路分析

首先我们还是要先理解一下题意，题目会给我们一个数组，数组代表河里每块石头的位置，现在有一只青蛙，需要借助这些石头过河，我们需要计算青蛙过河的的最小代价，这里的最小代价指的是青蛙在跳跃过程中的最大跳跃长度，一次跳跃的长度是青蛙跳跃前和跳跃后所在两块石头之间的距离。 而且青蛙不仅要跳过河，还需要跳回来，并且每颗石头都只能踩一次，也就是说跳跃过程中不可以踩到同一颗石头两次，而且还要保证花费最小的代价，我们需要尽可能让青蛙的每一步都更小步，那么也就是说我们应该要尽可能地使每一次跳跃跨越的石头更少，因为跳跃过程中不可以踩到同一颗石头两次，所以如果我们要想让所有石头都踩上一次的话，应该是每次跳跃要跨过一颗石头，这样来回跳跃的过程中踩到的石头刚好是交错的，我们只需要统计间隔一个石头的距离长度最大值即可，这样得到的最大值就是青蛙过河的最小代价。

如上图。如果跳跃的时候是直接跳到相邻的石头上，那么回程的时候则需要越过这两颗连续的石头，这样跳跃的距离肯会比下面这种情况要长，花费的代价会更大。

AC代码

完整代码如下：

/**
* @param {number[]} stones
* @return {number}
*/
var maxJump = function(stones) {
let res = stones[1] - stones[0];
for(let i = 0; i < stones.length - 2; i++){
res = Math.max(res,stones[i + 2] - stones[i]);
}
return res;
};

说在后面

本人为算法业余爱好者，平时只是随着兴趣偶尔刷刷题，如果上面分享有错误的地方，欢迎指出，感激不尽。 ------本页内容已结束，喜欢请分享------

感谢您的来访，获取更多精彩文章请收藏本站。