What is the pattern used in the Odd Even Jump problem?

The Odd Even Jump problem is a state transition dynamic programming problem that uses alternating odd and even jumps to traverse an array.

How do monotonic stacks help in solving the Odd Even Jump problem?

Monotonic stacks help by efficiently finding the next valid jump index for both odd and even numbered jumps, reducing the time complexity.

What is the time complexity of solving the Odd Even Jump problem?

The time complexity is O(n log n) due to sorting and the stack operations needed to find valid jumps for each index.

Can this problem be solved using brute force?

A brute-force solution is possible but inefficient, as it would likely exceed time limits due to the large number of comparisons required.

What are the edge cases to consider in the Odd Even Jump problem?

Edge cases include arrays with only one element, arrays where no valid starting index exists, or arrays where you are already at the last index.

#975

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

奇偶跳

给定一个整数数组 arr ，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。你可以按以下方式从索引 i 向后跳转到索引 j （其中 i ）：在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会…

数组动态规划栈排序单调栈

题目描述

给定一个整数数组 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：

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

示例 2：

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

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

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

在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 arr[3] 是（arr[3]，arr[4]）中大于或等于 arr[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）出发，通过一定数量的跳跃到达数组末尾。

示例 3：

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

提示：

1 <= arr.length <= 20000
0 <= arr[i] < 100000

lightbulb

解题思路

方法一：有序集合 + 记忆化搜索

我们先利用有序集合，预处理出每个位置能跳到的位置，记录在数组 $g$ 中，其中 $g[i][1]$ 和 $g[i][0]$ 分别表示当前位置是奇数次跳还是偶数次跳时能跳到的位置。如果不能跳到任何位置，那么 $g[i][1]$ 和 $g[i][0]$ 都为 $-1$ 。

然后利用记忆化搜索，从每个位置出发，且当前是奇数次跳跃，判断是否能跳到数组末尾，如果能，那么结果加一。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        @cache
        def dfs(i: int, k: int) -> bool:
            if i == n - 1:
                return True
            if g[i][k] == -1:
                return False
            return dfs(g[i][k], k ^ 1)

        n = len(arr)
        g = [[0] * 2 for _ in range(n)]
        sd = SortedDict()
        for i in range(n - 1, -1, -1):
            j = sd.bisect_left(arr[i])
            g[i][1] = sd.values()[j] if j < len(sd) else -1
            j = sd.bisect_right(arr[i]) - 1
            g[i][0] = sd.values()[j] if j >= 0 else -1
            sd[arr[i]] = i
        return sum(dfs(i, 1) for i in range(n))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding dynamic programming with alternating conditions is crucial for solving this problem efficiently.
question_mark
Candidate should demonstrate the ability to optimize time complexity, especially with the use of monotonic stacks.
question_mark
The ability to explain the transitions between states and why monotonic stacks help is key to a strong solution.

warning

常见陷阱

外企场景

error
Misunderstanding the conditions for odd and even jumps, leading to incorrect transitions between states.
error
Using brute-force solutions without utilizing sorting and stacks, which could lead to time-limit exceeded errors.
error
Failing to consider edge cases like already being at the end of the array or having no valid path.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider modifying the problem to find the minimum number of jumps to reach the end instead of counting valid starting indices.
arrow_right_alt
Extend the problem to support arrays with negative numbers or varying jump conditions.
arrow_right_alt
Instead of alternating odd and even jumps, alternate between forward and backward jumps to test different dynamic programming approaches.

help

常见问题

外企场景

继续练习

#907 子数组的最小值之和 #853 车队 #1130 叶值的最小代价生成树