1
2
3
4
5
6
7
8

输入：[10,13,12,14,15]
输出：2
解释： 
从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 A[2] 是 A[1]，A[2]，A[3]，A[4] 中大于或等于 A[0] 的最小值），然后我们就无法继续跳下去了。
从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

输入：[2,3,1,1,4]
输出：3
解释：
从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：

在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大于或等于 A[0] 的最小值。

在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 A[2] 是（A[2]，A[3]，A[4]）中小于或等于 A[1] 的最大值。A[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。

在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值。

我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。

类似地，我们可以推断：
从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。

1
2
3
4

输入：[5,1,3,4,2]
输出：3
解释： 
我们可以从起始索引 1，2，4 出发到达数组末尾。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

// @lc code=start
use std::collections::BTreeMap;

impl Solution {
    /// ## 解题思路
    /// - 动态规划+BTreeMap
    pub fn odd_even_jumps(arr: Vec<i32>) -> i32 {
        let mut good_count = 1; // 好索引的计数，最后一个总是可以到达，所以至少为1
        let mut odd = vec![false; arr.len()]; //每个索引位置是否经过奇数步跳跃到达终点；
        let mut even = vec![false; arr.len()]; //每个索引位置是否经过偶数步跳跃到达终点；
        *odd.last_mut().unwrap() = true;
        *even.last_mut().unwrap() = true;

        let mut map = BTreeMap::new(); //
        map.insert(*arr.last().unwrap(), arr.len() - 1);

        for i in (0..arr.len() - 1).rev() {
            let from = arr[i];
            // 在当前数字后面，存在>=当前数字的可跳数字
            if let Some((_, jump_index)) = map.range(from..).next() {
                // 当前位置可进行奇数跳跃，是否能抵达终点和下一个偶数起跳点是否能达到终点一样；
                odd[i] = even[*jump_index];
            }
            // 在当前数字后面，存在<=当前数字的可跳数字
            if let Some((_, jump_index)) = map.range(..=from).next_back() {
                // 当前位置可进行偶数跳跃，是否能抵达终点和下一个奇数起跳点是否能达到终点一样；
                even[i] = odd[*jump_index];
            }
            //如果当前位置可通过奇数起跳到达终点
            if odd[i] {
                good_count += 1; //则好的起始索引数量+1
            }
            //记录当前数字和索引
            map.insert(from, i);
        }
        good_count
    }
}
// @lc code=end
struct Solution;

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        assert_eq!(Solution::odd_even_jumps(vec![5, 1, 3, 4, 2]), 3);
    }
}