975-奇偶跳(Odd Even Jump)
发表于：2021-12-03 | 分类： 困难
字数统计: 2.7k | 阅读时长: 12分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/odd-even-jump

英文原文

You are given an integer array arr. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, ...) jumps in the series are called odd-numbered jumps, and the (2nd, 4th, 6th, ...) jumps in the series are called even-numbered jumps. Note that the jumps are numbered, not the indices.

You may jump forward from index i to index j (with i < j) in the following way:

  • During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index j such that arr[i] <= arr[j] and arr[j] is the smallest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
  • During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index j such that arr[i] >= arr[j] and arr[j] is the largest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
  • It may be the case that for some index i, there are no legal jumps.

A starting index is good if, starting from that index, you can reach the end of the array (index arr.length - 1) by jumping some number of times (possibly 0 or more than once).

Return the number of good starting indices.

 

Example 1:

Input: arr = [10,13,12,14,15]
Output: 2
Explanation: 
From starting index i = 0, we can make our 1st jump to i = 2 (since arr[2] is the smallest among arr[1], arr[2], arr[3], arr[4] that is greater or equal to arr[0]), then we cannot jump any more.
From starting index i = 1 and i = 2, we can make our 1st jump to i = 3, then we cannot jump any more.
From starting index i = 3, we can make our 1st jump to i = 4, so we have reached the end.
From starting index i = 4, we have reached the end already.
In total, there are 2 different starting indices i = 3 and i = 4, where we can reach the end with some number of
jumps.

Example 2:

Input: arr = [2,3,1,1,4]
Output: 3
Explanation: 
From starting index i = 0, we make jumps to i = 1, i = 2, i = 3:
During our 1st jump (odd-numbered), we first jump to i = 1 because arr[1] is the smallest value in [arr[1], arr[2], arr[3], arr[4]] that is greater than or equal to arr[0].
During our 2nd jump (even-numbered), we jump from i = 1 to i = 2 because arr[2] is the largest value in [arr[2], arr[3], arr[4]] that is less than or equal to arr[1]. arr[3] is also the largest value, but 2 is a smaller index, so we can only jump to i = 2 and not i = 3
During our 3rd jump (odd-numbered), we jump from i = 2 to i = 3 because arr[3] is the smallest value in [arr[3], arr[4]] that is greater than or equal to arr[2].
We can't jump from i = 3 to i = 4, so the starting index i = 0 is not good.
In a similar manner, we can deduce that:
From starting index i = 1, we jump to i = 4, so we reach the end.
From starting index i = 2, we jump to i = 3, and then we can't jump anymore.
From starting index i = 3, we jump to i = 4, so we reach the end.
From starting index i = 4, we are already at the end.
In total, there are 3 different starting indices i = 1, i = 3, and i = 4, where we can reach the end with some
number of jumps.

Example 3:

Input: arr = [5,1,3,4,2]
Output: 3
Explanation: We can reach the end from starting indices 1, 2, and 4.

 

Constraints:

  • 1 <= arr.length <= 2 * 104
  • 0 <= arr[i] < 105

中文题目

给定一个整数数组 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），那么该索引就会被认为是好的起始索引。

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

 

示例 1：

输入：[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）出发，通过一定数量的跳跃到达数组末尾。

示例 2：

输入：[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）出发，通过一定数量的跳跃到达数组末尾。

示例 3：

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

 

提示：

  1. 1 <= A.length <= 20000
  2. 0 <= A[i] < 100000

通过代码

官方题解

方法一：单调栈

思路

首先，我们可以发现下一步应该跳到哪里只与我们当前的位置与跳跃次数的奇偶性有关系。

对于每一种状态，接下来可以跳到的状态一定只有一种（或者接下来不能跳跃了）。如果我们使用某种方法知道了不同状态之间的转移关系，我们就可以通过一次简单的遍历解决这个问题了。

于是，问题就简化为了：从索引 i 进行奇数次跳跃时，下一步应该跳到哪里去（如果有的话）。偶数次跳跃也是类似的。

算法

假设当前是奇数次跳跃，让我们来搞清楚在索引 i 的位置接下来应该跳到哪里去。

我们从小到大考虑数组 A 中的元素。假设当前我们正在考虑 A[j] = v，在我们已经处理过但是还未确定下一步跳跃位置的索引中（也就是 <= v 的那些）进行搜索。 如果我们找到了某些已经处理过的值 v0 = A[i] 且 i < j，那么我们就可以知道从索引 i 下一步应该跳跃到索引 j 的位置。

这种朴素的方法有一点点慢，然而我们可以使用一个很常见的技巧 单调栈 来加速这个过程。

我们在栈中保存所有已经处理过的索引 i ，并且时时刻刻维护这个栈中的元素是递减的。当我们增加一个新的索引 j 的时候，我们弹出栈顶比较小的索引 i < j，并且记录这些索引下一步全都会跳跃到索引 j。

然后，我们就知道所有的 oddnext[i]，也就是位于索引 i 在奇数次跳跃时将会跳到的位置。使用类似的方法，我们也可以求出 evennext[i]。有了这些信息，我们就可以使用动态规划的技巧快速建立所有可达状态。

[DWr7gh22-Python]
class Solution(object):
    def oddEvenJumps(self, A):
        N = len(A)

        def make(B):
            ans = [None] * N
            stack = []  # invariant: stack is decreasing
            for i in B:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans

        B = sorted(range(N), key = lambda i: A[i])
        oddnext = make(B)
        B.sort(key = lambda i: -A[i])
        evennext = make(B)

        odd = [False] * N
        even = [False] * N
        odd[N-1] = even[N-1] = True

        for i in xrange(N-2, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]

        return sum(odd)

复杂度分析

  • 时间复杂度：$O(N \log N)$，其中 $N$ 是数组 A 的长度。

  • 空间复杂度：$O(N)$。

方法二： 树映射（Tree Map）

思路

在 方法一 中，原问题简化为：奇数次跳跃时，对于一些索引 i，下一步应该跳到哪里去（如果有的话）。

算法

我们可以使用 TreeMap，一个维护有序数据的绝佳数据结构。我们将索引 i 映射到 v = A[i] 上。

从 i = N-2 到 i = 0 的遍历过程中，对于 v = A[i]， 我们想知道比它略大一点和略小一点的元素是谁。 TreeMap.lowerKey 与 TreeMap.higherKey 函数就是用来做这样一件事情的。

了解这一点之后，解法接下来的内容就非常直接了： 我们使用动态规划来维护 odd[i] 和 even[i]：从索引 i 出发奇数次跳跃与偶数次跳跃是否能到达数组末尾。

[niMJSnZi-Java]
class Solution {
    public int oddEvenJumps(int[] A) {
        int N = A.length;
        if (N <= 1) return N;
        boolean[] odd = new boolean[N];
        boolean[] even = new boolean[N];
        odd[N-1] = even[N-1] = true;

        TreeMap<Integer, Integer> vals = new TreeMap();
        vals.put(A[N-1], N-1);
        for (int i = N-2; i >= 0; --i) {
            int v = A[i];
            if (vals.containsKey(v)) {
                odd[i] = even[vals.get(v)];
                even[i] = odd[vals.get(v)];
            } else {
                Integer lower = vals.lowerKey(v);
                Integer higher = vals.higherKey(v);

                if (lower != null)
                    even[i] = odd[vals.get(lower)];
                if (higher != null) {
                    odd[i] = even[vals.get(higher)];
                }
            }
            vals.put(v, i);
        }

        int ans = 0;
        for (boolean b: odd)
            if (b) ans++;
        return ans;
    }
}

复杂度分析

  • 时间复杂度：$O(N \log N)$，其中 $N$ 是数组 A 的长度。

  • 空间复杂度：$O(N)$。

统计信息

通过次数 提交次数 AC比率
3251 7240 44.9%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
动态规划 数组 栈 单调栈 有序集合
上一篇:
974-和可被 K 整除的子数组(Subarray Sums Divisible by K)
下一篇:
976-三角形的最大周长(Largest Perimeter Triangle)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo