0975. Odd Even Jump

题目信息

题号:

0975

难度:

Hard

主题:

数组、交替跳跃、好起点计数

原题:

LeetCode 0975

重点:

第一次跳跃为奇数次;奇数跳选择右侧不小于当前值的最小数值,偶数跳选择右侧不大于当前值的最大数值,数值并列时均取最小下标

题目重述

给定整数数组 arr。从某个下标 i 开始,第一次、第三次等奇数编号跳跃必须跳到右侧下标 j:要求 arr[j] >= arr[i],并在所有满足条件的值中选择最小的 arr[j];若该值出现多次,选择最小下标。

第二次、第四次等偶数编号跳跃要求 arr[j] <= arr[i],并选择其中最大的 arr[j],数值并列同样选最小下标。某次没有合法目标时路径终止。若从起点最终能到达最后一个下标,则该起点是好起点;最后一个下标自身也是好起点。请返回好起点数量。

1 <= arr.length <= 2 * 10^4,0 <= arr[i] < 10^5。

自建示例

只有一个非末尾起点能够到达终点:

输入:arr = [4,2,3,1]
输出:2
解释:从下标 1 奇数跳到值 3 的下标 2,再偶数跳到末尾值 1;末尾下标自身也是好起点。下标 0 和 2 都没有合法奇数跳。

数组只有一个元素:

输入:arr = [7]
输出:1
解释:唯一位置已经是最后一个下标,不需要跳跃,因此它是好起点。