青蛙过河 II

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

问题描述

给你一个下标从0开始的整数数组stones,数组中的元素严格递增,表示一条河中石头的位置。 一只青蛙一开始在第一块石头上,它想到达最后一块石头,然后回到第一块石头。同时每块石头至多到达一次。 一次跳跃的长度是青蛙跳跃前和跳跃后所在两块石头之间的距离。
  • 更正式的,如果青蛙从stones[i]跳到stones[j],跳跃的长度为|stones[i] - stones[j]|
一条路径的代价是这条路径里的最大跳跃长度。 请你返回这只青蛙的最小代价示例 1:
青蛙过河 II 插图1
输入: stones = [0,2,5,6,7]
输出: 5
解释: 上图展示了一条最优路径。
这条路径的代价是 5 ,是这条路径中的最大跳跃长度。
无法得到一条代价小于 5 的路径,我们返回 5 。
示例 2:
青蛙过河 II 插图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中的元素严格递增。

思路分析

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

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;
};

说在后面

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

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

© 版权声明
THE END
喜欢就支持一下吧
点赞11 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容