Hard
题目描述
给定一个整数数组 arr。从某个起始索引开始，你可以进行一系列跳跃。这个系列中的第（1、3、5…）次跳跃称为奇数跳跃，第（2、4、6…）次跳跃称为偶数跳跃。注意跳跃是按次数编号的，而不是按索引编号。
你可以按以下方式从索引 i 跳到索引 j（其中 i < j）：
- 在奇数跳跃期间（即跳跃 1、3、5…），你跳到索引
j，使得arr[i] <= arr[j]且arr[j]是可能的最小值。如果有多个这样的索引j，你只能跳到最小的索引j。 - 在偶数跳跃期间（即跳跃 2、4、6…），你跳到索引
j，使得arr[i] >= arr[j]且arr[j]是可能的最大值。如果有多个这样的索引j，你只能跳到最小的索引j。 - 对于某些索引
i，可能没有合法的跳跃。
如果从某个起始索引开始，你可以通过跳跃若干次（可能 0 次或多次）到达数组的末尾（索引 arr.length - 1），则该起始索引是好的。
返回好的起始索引的数量。
示例 1：
输入：arr = [10,13,12,14,15]
输出：2
解释：
从起始索引 i = 0，我们可以进行第1次跳跃到 i = 2（因为 arr[2] 是 arr[1], arr[2], arr[3], arr[4] 中大于等于 arr[0] 的最小值），然后我们无法再跳跃了。
从起始索引 i = 1 和 i = 2，我们可以进行第1次跳跃到 i = 3，然后我们无法再跳跃了。
从起始索引 i = 3，我们可以进行第1次跳跃到 i = 4，所以我们到达了末尾。
从起始索引 i = 4，我们已经在末尾了。
总共有2个不同的起始索引 i = 3 和 i = 4，我们可以通过若干次跳跃到达末尾。
示例 2：
输入：arr = [2,3,1,1,4]
输出：3
示例 3：
输入：arr = [5,1,3,4,2]
输出：3
提示：
1 <= arr.length <= 2 * 10^40 <= arr[i] < 10^5
解题思路
这个问题需要动态规划和单调栈的结合来解决。
核心思路：
- 对于每个位置，我们需要知道奇数跳跃和偶数跳跃能到达的下一个位置
- 使用动态规划记录从每个位置出发，进行奇数跳跃或偶数跳跃是否能到达终点
解决步骤：
首先需要预处理出每个位置的下一跳位置：
- 奇数跳跃：找到右边第一个大于等于当前值的最小值对应的索引
- 偶数跳跃：找到右边第一个小于等于当前值的最大值对应的索引
这可以通过排序 + 单调栈来高效实现：
- 将索引按值排序（奇数跳跃升序，偶数跳跃降序）
- 使用单调栈维护递增的索引序列，找到每个位置的下一个可跳跃位置
然后使用动态规划：
odd[i]表示从位置 i 开始奇数跳跃能否到达终点even[i]表示从位置 i 开始偶数跳跃能否到达终点
状态转移：
odd[i] = even[nextOdd[i]]（奇数跳跃后变成偶数跳跃）even[i] = odd[nextEven[i]]（偶数跳跃后变成奇数跳跃）
推荐解法： 单调栈 + 动态规划，时间复杂度最优。
代码实现
class Solution {
public:
int oddEvenJumps(vector<int>& arr) {
int n = arr.size();
vector<int> nextOdd(n, -1), nextEven(n, -1);
// 计算奇数跳跃的下一个位置
map<int, int> mp;
for (int i = n - 1; i >= 0; i--) {
auto it = mp.lower_bound(arr[i]);
if (it != mp.end()) {
nextOdd[i] = it->second;
}
mp[arr[i]] = i;
}
// 计算偶数跳跃的下一个位置
mp.clear();
for (int i = n - 1; i >= 0; i--) {
auto it = mp.upper_bound(arr[i]);
if (it != mp.begin()) {
--it;
nextEven[i] = it->second;
}
mp[arr[i]] = i;
}
// 动态规划
vector<bool> odd(n, false), even(n, false);
odd[n - 1] = even[n - 1] = true;
int result = 1;
for (int i = n - 2; i >= 0; i--) {
if (nextOdd[i] != -1) {
odd[i] = even[nextOdd[i]];
}
if (nextEven[i] != -1) {
even[i] = odd[nextEven[i]];
}
if (odd[i]) result++;
}
return result;
}
};
class Solution:
def oddEvenJumps(self, arr: List[int]) -> int:
from bisect import bisect_left
n = len(arr)
next_odd = [-1] * n
next_even = [-1] * n
# 计算奇数跳跃的下一个位置
sorted_indices = []
values = []
for i in range(n - 1, -1, -1):
pos = bisect_left(values, arr[i])
if pos < len(values):
next_odd[i] = sorted_indices[pos]
# 插入当前元素，保持有序
insert_pos = bisect_left(values, arr[i])
values.insert(insert_pos, arr[i])
sorted_indices.insert(insert_pos, i)
# 计算偶数跳跃的下一个位置
sorted_indices = []
values = []
for i in range(n - 1, -1, -1):
pos = bisect_left(values, arr[i])
if pos > 0:
next_even[i] = sorted_indices[pos - 1]
elif pos == 0 and values and values[0] == arr[i]:
next_even[i] = sorted_indices[0]
# 插入当前元素，保持有序（降序）
insert_pos = bisect_left(values, arr[i])
if insert_pos == len(values) or values[insert_pos] != arr[i]:
values.insert(insert_pos, arr[i])
sorted_indices.insert(insert_pos, i)
else:
# 相同值，选择较小的索引
if i < sorted_indices[insert_pos]:
sorted_indices[insert_pos] = i
# 重新计算偶数跳跃
indices_by_value = {}
for i in range(n - 1, -1, -1):
indices_by_value[arr[i]] = i
sorted_vals = sorted(indices_by_value.keys(), reverse=True)
for i in range(n - 1, -1, -1):
pos = bisect_left(sorted_vals, arr[i])
if pos < len(sorted_vals):
next_even[i] = indices_by_value[sorted_vals[pos]]
# 简化计算
sorted_items = sorted((arr[i], i) for i in range(n))
for i in range(n):
next_odd[i] = -1
for i in range(len(sorted_items) - 1):
val1, idx1 = sorted_items[i]
val2, idx2 = sorted_items[i + 1]
if val1 == val2:
continue
for j in range(idx1):
if arr[j] <= val1 and next_odd[j] == -1:
next_odd[j] = idx1
# 重新实现
def find_next_jumps():
next_odd = [-1] * n
next_even = [-1] * n
# 对于奇数跳跃，按值升序、索引升序排序
indices = list(range(n))
indices.sort(key=lambda i: (arr[i], i))
stack = []
for i in indices:
while stack and stack[-1] < i:
next_odd[stack.pop()] = i
stack.append(i)
# 对于偶数跳跃，按值降序、索引升序排序
indices.sort(key=lambda i: (-arr[i], i))
stack = []
for i in indices:
while stack and stack[-1] < i:
next_even[stack.pop()] = i
stack.append(i)
return next_odd, next_even
next_odd, next_even = find_next_jumps()
# 动态规划
odd = [False] * n
even = [False] * n
odd[n - 1] = even[n - 1] = True
result = 1
for i in range(n - 2, -1, -1):
if next_odd[i] != -1:
odd[i] = even[next_odd[i]]
if next_even[i] != -1:
even[i] = odd[next_even[i]]
if odd[i]:
result += 1
return result
public class Solution {
public int OddEvenJumps(int[] arr) {
int n = arr.Length;
int[] nextOdd = new int[n];
int[] nextEven = new int[n];
Array.Fill(nextOdd, -1);
Array.Fill(nextEven, -1);
// 计算奇数跳跃的下一个位置
var sortedMap = new SortedDictionary<int, int>();
for (int i = n - 1; i >= 0; i--) {
var found = sortedMap.FirstOrDefault(x => x.Key >= arr[i]);
if (found.Key != 0) {
nextOdd[i] = found.Value;
}
sortedMap[arr[i]] = i;
}
// 计算偶数跳跃的下一个位置
sortedMap.Clear();
for (int i = n - 1; i >= 0; i--) {
var found = sortedMap.LastOrDefault(x => x.Key <= arr[i]);
if (found.Key != 0 || (found.Key == 0 && sortedMap.ContainsKey(0))) {
nextEven[i] = found.Value;
}
sortedMap[arr[i]] = i;
}
// 动态规划
bool[] odd = new bool[n];
bool[] even = new bool[n];
odd[n - 1] = even[n - 1] = true;
int result = 1;
for (int i = n - 2; i >= 0; i--) {
if (nextOdd[i] != -1) {
odd[i] = even[nextOdd[i]];
}
if (nextEven[i] != -1) {
even[i] = odd[nextEven[i]];
}
if (odd[i]) result++;
}
return result;
}
}
var oddEvenJumps = function(arr) {
const n = arr.length;
const nextOdd = new Array(n).fill(-1);
const nextEven = new Array(n).fill(-1);
// 计算奇数跳跃的下一个位置 - 使用单调栈
const indices = Array.from({length: n}, (_, i) => i);
indices.sort((i, j) => arr[i]
复杂度分析
| 解