LeetCode 975: Odd Even Jump (Ordered Map + Reverse DP)
LeetCode 975Ordered MapDPToday we solve LeetCode 975 - Odd Even Jump.
Source: https://leetcode.com/problems/odd-even-jump/
English
Problem Summary
From index i, odd jumps must go to the smallest index j > i with arr[j] >= arr[i] and minimal value. Even jumps must go to the smallest index j > i with arr[j] <= arr[i] and maximal value. Count starting indices that can finally reach the last index.
Key Insight
Define DP states from right to left: oddGood[i] means starting at i with an odd jump can reach the end, evenGood[i] for an even jump. If we know each index's next odd target and next even target, transitions are direct.
Algorithm
- Build nextHigher[i] and nextLower[i] using monotonic stack over indices sorted by value (ascending for odd, descending for even).
- Initialize oddGood[n-1] = evenGood[n-1] = true.
- Traverse i from right to left:
• if nextHigher[i] != -1, then oddGood[i] = evenGood[nextHigher[i]]
• if nextLower[i] != -1, then evenGood[i] = oddGood[nextLower[i]]
- Count indices where oddGood[i] is true.
Complexity Analysis
Let n be array length.
Time: O(n log n) (sorting dominates).
Space: O(n).
Common Pitfalls
- Wrong tie-break on equal values. We must pick the smallest valid index, so sort by value then index.
- Mixing odd/even transition directions.
- Forgetting that the last index is always good.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int oddEvenJumps(int[] arr) {
int n = arr.length;
int[] nextHigher = buildNext(arr, true);
int[] nextLower = buildNext(arr, false);
boolean[] oddGood = new boolean[n];
boolean[] evenGood = new boolean[n];
oddGood[n - 1] = true;
evenGood[n - 1] = true;
int ans = 1;
for (int i = n - 2; i >= 0; i--) {
if (nextHigher[i] != -1) oddGood[i] = evenGood[nextHigher[i]];
if (nextLower[i] != -1) evenGood[i] = oddGood[nextLower[i]];
if (oddGood[i]) ans++;
}
return ans;
}
private int[] buildNext(int[] arr, boolean ascending) {
int n = arr.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> {
if (arr[a] != arr[b]) {
return ascending ? Integer.compare(arr[a], arr[b]) : Integer.compare(arr[b], arr[a]);
}
return Integer.compare(a, b);
});
int[] next = new int[n];
Arrays.fill(next, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i : idx) {
while (!st.isEmpty() && i > st.peek()) {
next[st.pop()] = i;
}
st.push(i);
}
return next;
}
}package main
import "sort"
func oddEvenJumps(arr []int) int {
n := len(arr)
nextHigher := buildNext(arr, true)
nextLower := buildNext(arr, false)
oddGood := make([]bool, n)
evenGood := make([]bool, n)
oddGood[n-1], evenGood[n-1] = true, true
ans := 1
for i := n - 2; i >= 0; i-- {
if nextHigher[i] != -1 {
oddGood[i] = evenGood[nextHigher[i]]
}
if nextLower[i] != -1 {
evenGood[i] = oddGood[nextLower[i]]
}
if oddGood[i] {
ans++
}
}
return ans
}
func buildNext(arr []int, asc bool) []int {
n := len(arr)
idx := make([]int, n)
for i := 0; i < n; i++ {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool {
a, b := idx[i], idx[j]
if arr[a] != arr[b] {
if asc {
return arr[a] < arr[b]
}
return arr[a] > arr[b]
}
return a < b
})
next := make([]int, n)
for i := range next {
next[i] = -1
}
st := make([]int, 0)
for _, i := range idx {
for len(st) > 0 && i > st[len(st)-1] {
top := st[len(st)-1]
st = st[:len(st)-1]
next[top] = i
}
st = append(st, i)
}
return next
}class Solution {
public:
int oddEvenJumps(vector<int>& arr) {
int n = (int)arr.size();
vector<int> nextHigher = buildNext(arr, true);
vector<int> nextLower = buildNext(arr, false);
vector<bool> oddGood(n, false), evenGood(n, false);
oddGood[n - 1] = true;
evenGood[n - 1] = true;
int ans = 1;
for (int i = n - 2; i >= 0; --i) {
if (nextHigher[i] != -1) oddGood[i] = evenGood[nextHigher[i]];
if (nextLower[i] != -1) evenGood[i] = oddGood[nextLower[i]];
if (oddGood[i]) ++ans;
}
return ans;
}
private:
vector<int> buildNext(const vector<int>& arr, bool asc) {
int n = (int)arr.size();
vector<int> idx(n), next(n, -1);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b) {
if (arr[a] != arr[b]) {
return asc ? arr[a] < arr[b] : arr[a] > arr[b];
}
return a < b;
});
vector<int> st;
for (int i : idx) {
while (!st.empty() && i > st.back()) {
next[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
return next;
}
};from typing import List
class Solution:
def oddEvenJumps(self, arr: List[int]) -> int:
n = len(arr)
next_higher = self._build_next(arr, asc=True)
next_lower = self._build_next(arr, asc=False)
odd_good = [False] * n
even_good = [False] * n
odd_good[-1] = True
even_good[-1] = True
ans = 1
for i in range(n - 2, -1, -1):
if next_higher[i] != -1:
odd_good[i] = even_good[next_higher[i]]
if next_lower[i] != -1:
even_good[i] = odd_good[next_lower[i]]
if odd_good[i]:
ans += 1
return ans
def _build_next(self, arr: List[int], asc: bool) -> List[int]:
n = len(arr)
idx = list(range(n))
idx.sort(key=lambda i: (arr[i], i) if asc else (-arr[i], i))
nxt = [-1] * n
st = []
for i in idx:
while st and i > st[-1]:
nxt[st.pop()] = i
st.append(i)
return nxtvar oddEvenJumps = function(arr) {
const n = arr.length;
const nextHigher = buildNext(arr, true);
const nextLower = buildNext(arr, false);
const oddGood = new Array(n).fill(false);
const evenGood = new Array(n).fill(false);
oddGood[n - 1] = true;
evenGood[n - 1] = true;
let ans = 1;
for (let i = n - 2; i >= 0; i--) {
if (nextHigher[i] !== -1) oddGood[i] = evenGood[nextHigher[i]];
if (nextLower[i] !== -1) evenGood[i] = oddGood[nextLower[i]];
if (oddGood[i]) ans++;
}
return ans;
};
function buildNext(arr, asc) {
const n = arr.length;
const idx = Array.from({ length: n }, (_, i) => i);
idx.sort((a, b) => {
if (arr[a] !== arr[b]) return asc ? arr[a] - arr[b] : arr[b] - arr[a];
return a - b;
});
const next = new Array(n).fill(-1);
const st = [];
for (const i of idx) {
while (st.length && i > st[st.length - 1]) {
next[st.pop()] = i;
}
st.push(i);
}
return next;
}中文
题目概述
从下标 i 出发，奇数跳要跳到满足 j > i 且 arr[j] >= arr[i] 的最小值位置（值最小，若并列取下标最小）；偶数跳要跳到满足 arr[j] <= arr[i] 的最大值位置（并列同样取下标最小）。求有多少个起点能到达最后一个下标。
核心思路
从右往左做动态规划：oddGood[i] 表示从 i 开始执行奇数跳是否能到终点，evenGood[i] 表示从 i 开始执行偶数跳是否能到终点。关键是先预处理每个位置的下一跳目标。
算法步骤
- 通过“按值排序 + 单调栈”构造 nextHigher 和 nextLower。
- 终点初始化：oddGood[n-1] = evenGood[n-1] = true。
- 从右到左转移：
• oddGood[i] = evenGood[nextHigher[i]]（若存在）
• evenGood[i] = oddGood[nextLower[i]]（若存在）
- 最终统计 oddGood[i] == true 的个数。
复杂度分析
设数组长度为 n。
时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(n)。
常见陷阱
- 相同数值时没有按“下标更小优先”处理，导致目标点错误。
- 奇偶跳状态转移写反。
- 忘记最后一个位置天然可达。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int oddEvenJumps(int[] arr) {
int n = arr.length;
int[] nextHigher = buildNext(arr, true);
int[] nextLower = buildNext(arr, false);
boolean[] oddGood = new boolean[n];
boolean[] evenGood = new boolean[n];
oddGood[n - 1] = true;
evenGood[n - 1] = true;
int ans = 1;
for (int i = n - 2; i >= 0; i--) {
if (nextHigher[i] != -1) oddGood[i] = evenGood[nextHigher[i]];
if (nextLower[i] != -1) evenGood[i] = oddGood[nextLower[i]];
if (oddGood[i]) ans++;
}
return ans;
}
private int[] buildNext(int[] arr, boolean ascending) {
int n = arr.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> {
if (arr[a] != arr[b]) {
return ascending ? Integer.compare(arr[a], arr[b]) : Integer.compare(arr[b], arr[a]);
}
return Integer.compare(a, b);
});
int[] next = new int[n];
Arrays.fill(next, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i : idx) {
while (!st.isEmpty() && i > st.peek()) {
next[st.pop()] = i;
}
st.push(i);
}
return next;
}
}package main
import "sort"
func oddEvenJumps(arr []int) int {
n := len(arr)
nextHigher := buildNext(arr, true)
nextLower := buildNext(arr, false)
oddGood := make([]bool, n)
evenGood := make([]bool, n)
oddGood[n-1], evenGood[n-1] = true, true
ans := 1
for i := n - 2; i >= 0; i-- {
if nextHigher[i] != -1 {
oddGood[i] = evenGood[nextHigher[i]]
}
if nextLower[i] != -1 {
evenGood[i] = oddGood[nextLower[i]]
}
if oddGood[i] {
ans++
}
}
return ans
}
func buildNext(arr []int, asc bool) []int {
n := len(arr)
idx := make([]int, n)
for i := 0; i < n; i++ {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool {
a, b := idx[i], idx[j]
if arr[a] != arr[b] {
if asc {
return arr[a] < arr[b]
}
return arr[a] > arr[b]
}
return a < b
})
next := make([]int, n)
for i := range next {
next[i] = -1
}
st := make([]int, 0)
for _, i := range idx {
for len(st) > 0 && i > st[len(st)-1] {
top := st[len(st)-1]
st = st[:len(st)-1]
next[top] = i
}
st = append(st, i)
}
return next
}class Solution {
public:
int oddEvenJumps(vector<int>& arr) {
int n = (int)arr.size();
vector<int> nextHigher = buildNext(arr, true);
vector<int> nextLower = buildNext(arr, false);
vector<bool> oddGood(n, false), evenGood(n, false);
oddGood[n - 1] = true;
evenGood[n - 1] = true;
int ans = 1;
for (int i = n - 2; i >= 0; --i) {
if (nextHigher[i] != -1) oddGood[i] = evenGood[nextHigher[i]];
if (nextLower[i] != -1) evenGood[i] = oddGood[nextLower[i]];
if (oddGood[i]) ++ans;
}
return ans;
}
private:
vector<int> buildNext(const vector<int>& arr, bool asc) {
int n = (int)arr.size();
vector<int> idx(n), next(n, -1);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b) {
if (arr[a] != arr[b]) {
return asc ? arr[a] < arr[b] : arr[a] > arr[b];
}
return a < b;
});
vector<int> st;
for (int i : idx) {
while (!st.empty() && i > st.back()) {
next[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
return next;
}
};from typing import List
class Solution:
def oddEvenJumps(self, arr: List[int]) -> int:
n = len(arr)
next_higher = self._build_next(arr, asc=True)
next_lower = self._build_next(arr, asc=False)
odd_good = [False] * n
even_good = [False] * n
odd_good[-1] = True
even_good[-1] = True
ans = 1
for i in range(n - 2, -1, -1):
if next_higher[i] != -1:
odd_good[i] = even_good[next_higher[i]]
if next_lower[i] != -1:
even_good[i] = odd_good[next_lower[i]]
if odd_good[i]:
ans += 1
return ans
def _build_next(self, arr: List[int], asc: bool) -> List[int]:
n = len(arr)
idx = list(range(n))
idx.sort(key=lambda i: (arr[i], i) if asc else (-arr[i], i))
nxt = [-1] * n
st = []
for i in idx:
while st and i > st[-1]:
nxt[st.pop()] = i
st.append(i)
return nxtvar oddEvenJumps = function(arr) {
const n = arr.length;
const nextHigher = buildNext(arr, true);
const nextLower = buildNext(arr, false);
const oddGood = new Array(n).fill(false);
const evenGood = new Array(n).fill(false);
oddGood[n - 1] = true;
evenGood[n - 1] = true;
let ans = 1;
for (let i = n - 2; i >= 0; i--) {
if (nextHigher[i] !== -1) oddGood[i] = evenGood[nextHigher[i]];
if (nextLower[i] !== -1) evenGood[i] = oddGood[nextLower[i]];
if (oddGood[i]) ans++;
}
return ans;
};
function buildNext(arr, asc) {
const n = arr.length;
const idx = Array.from({ length: n }, (_, i) => i);
idx.sort((a, b) => {
if (arr[a] !== arr[b]) return asc ? arr[a] - arr[b] : arr[b] - arr[a];
return a - b;
});
const next = new Array(n).fill(-1);
const st = [];
for (const i of idx) {
while (st.length && i > st[st.length - 1]) {
next[st.pop()] = i;
}
st.push(i);
}
return next;
}
Comments