2023-05-31：给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数

在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃

而第 2、4、6... 次跳跃称为偶数跳跃

你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：

在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j

使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多个这样的索引 j

你只能跳到满足要求的最小索引 j 上。

在进行偶数跳跃时（如，第 2，4，6... 次跳跃）

你将会跳到索引 j，使得 A[i] >= A[j]，A[j] 是可能的最大值

如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。

（对于某些索引 i，可能无法进行合乎要求的跳跃。）

如果从某一索引开始跳跃一定次数（可能是 0 次或多次）

就可以到达数组的末尾（索引 A.length - 1）

那么该索引就会被认为是好的起始索引。

返回好的起始索引的数量。

输入：[2,3,1,1,4]。

输出：3。

答案2023-05-31：

大体步骤如下：

1.对于数组中的每个元素，使用有序表（treemap）分别找到奇数规则和偶数规则下的下一步位置。

2.奇数规则下要寻找第一个大于等于当前值的位置，而偶数规则下要寻找第一个小于等于当前值的位置。

3.使用动态规划方法，从后往前遍历数组，对于每个位置分别判断是否能够到达数组的末尾。

4.定义 dp[i][0] 表示当来到 i 位置，且在奇数规则下，最终能否到达数组末尾。同理，dp[i][1] 表示当来到 i 位置，且在偶数规则下，最终能否到达数组末尾。

5.对于每个位置 i，如果奇数规则下可以跳到下一个位置 odd[i]，则 dp[i][0] = dp[odd[i]][1]。同理，如果偶数规则下可以跳到下一个位置 even[i]，则 dp[i][1] = dp[even[i]][0]。

6.初始化 dp[n-1][0] 和 dp[n-1][1] 为 true，表示从数组末尾出发，无论是奇数规则还是偶数规则，都可以到达该位置。

7.遍历数组，对于每个位置 i，如果 dp[i][0] = true，则说明从该位置出发遵循奇数规则可以到达数组末尾，答案加 1。

8.返回答案。

时间复杂度：在该算法中，使用了一次 treemap 的查询操作和一次 treemap 的插入操作，这两种操作的时间复杂度均为 O(log n)，对于遍历整个数组以及动态规划的过程，其时间复杂度均为 O(n)，因此总的时间复杂度为 O(n log n)。

空间复杂度：算法中使用三个数组以及一个有序表。其中 odd 和 even 数组的长度为 n，dp 数组的大小为 n * 2，而有序表需要存储 n 个元素，因此算法的空间复杂度为 O(n)。

go语言完整代码如下：

package main

import (
	"fmt"

	"github.com/emirpasic/gods/maps/treemap"
)

func oddEvenJumps(arr []int) int {
	n := len(arr)
	// 来到了i位置，如果要遵循奇数规则，应该去哪？odd[i]
	odd := make([]int, n)
	// 来到了i位置，如果要遵循偶数规则，应该去哪？even[i]
	even := make([]int, n)
	// 有序表，
	// key : 某个值
	// value : key这个值，出现的最左位置
	// >= key 且最小
	// <= key 且最大
	orderMap := treemap.NewWithIntComparator()
	for i := n - 1; i >= 0; i-- {
		// i位置，arr[i]，奇数规则，>= arr[i]且最小的！
		to, to2 := orderMap.Ceiling(arr[i])
		if to != nil {
			odd[i] = to2.(int)
		} else {
			odd[i] = -1
		}
		// i位置，arr[i]，偶数规则，<= arr[i]且最大的！
		to, to2 = orderMap.Floor(arr[i])
		if to != nil {
			even[i] = to2.(int)
		} else {
			even[i] = -1
		}
		orderMap.Put(arr[i], i)
	}
	// dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾？
	// dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾？
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, 2)
	}
	dp[n-1][0] = true
	dp[n-1][1] = true
	ans := 1
	for i := n - 2; i >= 0; i-- {
		// dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾
		// odd[i] -> 右走！ -1
		if odd[i] != -1 {
			dp[i][0] = dp[odd[i]][1]
		}
		// dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾
		if even[i] != -1 {
			dp[i][1] = dp[even[i]][0]
		}
		if dp[i][0] {
			ans++
		}
	}
	return ans
}

func main() {
	arr := []int{2, 3, 1, 1, 4}
	result := oddEvenJumps(arr)
	fmt.Println(result)
}

rust语言完整代码如下：

use std::collections::BTreeMap;

fn odd_even_jumps(arr: Vec<i32>) -> i32 {
    let n = arr.len();
    // 来到了i位置，如果要遵循奇数规则，应该去哪？odd[i]
    let mut odd = vec![0; n];
    // 来到了i位置，如果要遵循偶数规则，应该去哪？even[i]
    let mut even = vec![0; n];
    // 有序表，
    // key : 某个值
    // value : key这个值，出现的最左位置
    // >= key 且最小
    // <= key 且最大
    let mut order_map = BTreeMap::new();
    let mut i = n as i32 - 1;
    while i >= 0 {
        // i位置，arr[i]，奇数规则，>= arr[i]且最小的！
        if let Some((&_to, &to2)) = order_map.range(arr[i as usize]..).next() {
            odd[i as usize] = to2;
        } else {
            odd[i as usize] = -1;
        }
        // i位置，arr[i]，偶数规则，<= arr[i]且最大的！
        if let Some((&_to, &to2)) = order_map.range(..=arr[i as usize]).rev().next() {
            even[i as usize] = to2;
        } else {
            even[i as usize] = -1;
        }
        order_map.insert(arr[i as usize], i);
        i -= 1;
    }
    // dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾？
    // dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾？
    let mut dp = vec![vec![false; 2]; n];
    dp[n - 1][0] = true;
    dp[n - 1][1] = true;
    let mut ans = 1;
    let mut i = n as i32 - 2;
    while i >= 0 {
        // dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾
        // odd[i] -> 右走！ -1
        dp[i as usize][0] = odd[i as usize] != -1 && dp[odd[i as usize] as usize][1];
        // dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾
        dp[i as usize][1] = even[i as usize] != -1 && dp[even[i as usize] as usize][0];
        ans += if dp[i as usize][0] { 1 } else { 0 };
        i -= 1;
    }
    ans
}

fn main() {
    let arr = vec![2,3,1,1,4];
    let result = odd_even_jumps(arr);
    println!("{}", result);
}

c++完整代码如下：

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int oddEvenJumps(vector<int>& arr) {
	int n = arr.size();
	// 来到了i位置，如果要遵循奇数规则，应该去哪？odd[i]
	vector<int> odd(n);
	// 来到了i位置，如果要遵循偶数规则，应该去哪？even[i]
	vector<int> even(n);
	// 有序表，
	// key : 某个值
	// value : key这个值，出现的最左位置
	// >= key 且最小
	// <= key 且最大
	map<int, int> orderMap;
	for (int i = n - 1; i >= 0; --i) {
		// i位置，arr[i]，奇数规则，>= arr[i]且最小的！
		auto it = orderMap.lower_bound(arr[i]);
		if (it != orderMap.end()) {
			odd[i] = it->second;
		}
		else {
			odd[i] = -1;
		}
		// i位置，arr[i]，偶数规则，<= arr[i]且最大的！
		it = orderMap.upper_bound(arr[i]);
		if (it != orderMap.begin()) {
			even[i] = (--it)->second;
		}
		else {
			even[i] = -1;
		}
		orderMap[arr[i]] = i;
	}
	// dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾？
	// dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾？
	vector<vector<bool>> dp(n, vector<bool>(2));
	dp[n - 1][0] = true;
	dp[n - 1][1] = true;
	int ans = 1;
	for (int i = n - 2; i >= 0; --i) {
		// dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾
		// odd[i] -> 右走！ -1
		if (odd[i] != -1) {
			dp[i][0] = dp[odd[i]][1];
		}
		// dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾
		if (even[i] != -1) {
			dp[i][1] = dp[even[i]][0];
		}
		if (dp[i][0]) {
			++ans;
		}
	}
	return ans;
}

int main() {
	vector<int> arr = { 2,3,1,1,4 };
	int result = oddEvenJumps(arr);
	cout << result << endl;
	return 0;
}

c语言完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct BTreeNode {
    int key;
    int value;
    struct BTreeNode* left;
    struct BTreeNode* right;
};

struct BTreeMap {
    struct BTreeNode* root;
};

struct BTreeNode* createNode(int key, int value) {
    struct BTreeNode* node = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
    node->key = key;
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct BTreeNode* insertNode(struct BTreeNode* node, int key, int value) {
    if (node == NULL) {
        return createNode(key, value);
    }
    if (key < node->key) {
        node->left = insertNode(node->left, key, value);
    }
    else if (key > node->key) {
        node->right = insertNode(node->right, key, value);
    }
    else {
        node->value = value;
    }
    return node;
}

struct BTreeNode* findCeiling(struct BTreeNode* node, int target) {
    if (node == NULL) {
        return NULL;
    }
    if (node->key == target) {
        return node;
    }
    if (node->key < target) {
        return findCeiling(node->right, target);
    }
    struct BTreeNode* leftNode = findCeiling(node->left, target);
    if (leftNode != NULL) {
        return leftNode;
    }
    return node;
}

struct BTreeNode* findFloor(struct BTreeNode* node, int target) {
    if (node == NULL) {
        return NULL;
    }
    if (node->key == target) {
        return node;
    }
    if (node->key > target) {
        return findFloor(node->left, target);
    }
    struct BTreeNode* rightNode = findFloor(node->right, target);
    if (rightNode != NULL) {
        return rightNode;
    }
    return node;
}

struct BTreeMap* createMap() {
    struct BTreeMap* map = (struct BTreeMap*)malloc(sizeof(struct BTreeMap));
    map->root = NULL;
    return map;
}

void insert(struct BTreeMap* map, int key, int value) {
    map->root = insertNode(map->root, key, value);
}

int getCeiling(struct BTreeMap* map, int target) {
    struct BTreeNode* ceilingNode = findCeiling(map->root, target);
    if (ceilingNode == NULL) {
        return -1;
    }
    return ceilingNode->value;
}

int getFloor(struct BTreeMap* map, int target) {
    struct BTreeNode* floorNode = findFloor(map->root, target);
    if (floorNode == NULL) {
        return -1;
    }
    return floorNode->value;
}

void destroyNode(struct BTreeNode* node) {
    if (node == NULL) {
        return;
    }
    destroyNode(node->left);
    destroyNode(node->right);
    free(node);
}

void destroyMap(struct BTreeMap* map) {
    destroyNode(map->root);
    free(map);
}

int oddEvenJumps(int* arr, int arrSize) {
    int n = arrSize;
    // 来到了i位置，如果要遵循奇数规则，应该去哪？odd[i]
    int* odd = (int*)malloc(n * sizeof(int));
    // 来到了i位置，如果要遵循偶数规则，应该去哪？even[i]
    int* even = (int*)malloc(n * sizeof(int));
    // 有序表，
    // key : 某个值
    // value : key这个值，出现的最左位置
    // >= key 且最小
    // <= key 且最大
    struct BTreeMap* orderMap = createMap();
    for (int i = n - 1; i >= 0; --i) {
        // i位置，arr[i]，奇数规则，>= arr[i]且最小的！
        int to2 = getCeiling(orderMap, arr[i]);
        if (to2 == -1) {
            odd[i] = -1;
        }
        else {
            odd[i] = to2;
        }
        // i位置，arr[i]，偶数规则，<= arr[i]且最大的！
        to2 = getFloor(orderMap, arr[i]);
        if (to2 == -1) {
            even[i] = -1;
        }
        else {
            even[i] = to2;
        }
        insert(orderMap, arr[i], i);
    }
    destroyMap(orderMap);
    // dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾？
    // dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾？
    bool** dp = (bool**)malloc(n * sizeof(bool*));
    for (int i = 0; i < n; ++i) {
        dp[i] = (bool*)malloc(2 * sizeof(bool));
        dp[i][0] = false;
        dp[i][1] = false;
    }
    dp[n - 1][0] = true;
    dp[n - 1][1] = true;
    int ans = 1;
    for (int i = n - 2; i >= 0; --i) {
        // dp[i][0] : 当来到i位置，且在奇数规则下，最终能不能到结尾
        // odd[i] -> 右走！ -1
        if (odd[i] != -1) {
            dp[i][0] = dp[odd[i]][1];
        }
        // dp[i][1] : 当来到i位置，且在偶数规则下，最终能不能到结尾
        if (even[i] != -1) {
            dp[i][1] = dp[even[i]][0];
        }
        if (dp[i][0]) {
            ++ans;
        }
    }
    // 释放内存
    for (int i = 0; i < n; ++i) {
        free(dp[i]);
    }
    free(dp);
    free(odd);
    free(even);
    return ans;
}

int main() {
    int arr[] = { 2,3,1,1,4 };
    int arrSize = sizeof(arr) / sizeof(int);
    int result = oddEvenJumps(arr, arrSize);
    printf("%d\n", result); 
    return 0;
}

本栏目推荐文章
• 类模板实现简单的数组
• 用于PostgreSQL索引维护的有用查询
• 索引的一些总结
• 数组内存图
• 数组
• 整数的划分（递归或动态规划）
• 1.12_redis 的存取在最后 晚上_浙江本地环境的header不能用线上的_header中host和refer分别代表什么意思?_模型的save()参数是数组怎么理解?
• 吴师兄学算法day06 双指针 80. 合并两个有序数组
• C# 方法中的参数数组
• 吴师兄学算法day06 双指针 26. 删除有序数组中的重复项

奇数 偶数 整数 数组 索引奇数 偶数 整数 数组 奇数 偶数 数组 顺序 奇数 偶数 数组 数组 奇数 偶数 奇数 偶数 升序 数组 数组 元素 偶数 整数 倍数 奇数 偶数 内存条 奇数 偶数 还是 数字 奇数 偶数 乘法表 奇数 偶数 乘法