feat: $975

lucifer · lucifer · commit a7e21cce8a31 · 2021-01-14T18:30:06.000+08:00
diff --git a/collections/hard.md b/collections/hard.md
@@ -54,6 +54,7 @@
 - [0768. 最多能完成排序的块 II](../problems/768.max-chunks-to-make-sorted-ii.md) 91
 - [0887. 鸡蛋掉落](../problems/887.super-egg-drop.md)
 - [0895. 最大频率栈](../problems/895.maximum-frequency-stack.md)
+- [0975. 奇偶跳](../problems/975.odd-even-jump.md) 🆕
 - [1032. 字符流](../problems/1032.stream-of-characters.md)
 - [1168. 水资源分配优化](../problems/1168.optimize-water-distribution-in-a-village.md)
 - [1203. 项目管理](../problems/1203.sort-items-by-groups-respecting-dependencies.md) 🆕
diff --git a/problems/975.odd-even-jump.md b/problems/975.odd-even-jump.md
@@ -0,0 +1,195 @@
+## 题目地址 (975. 奇偶跳）
+
+https://leetcode-cn.com/problems/odd-even-jump/
+
+## 题目描述
+
+```
+给定一个整数数组 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 <= A.length <= 20000
+0 <= A[i] < 100000
+
+```
+
+## 前置知识
+
+- [单调栈](../thinkings/monotone-stack.md)
+
+## 公司
+
+- 暂无
+
+## 思路
+
+题目要求我们从数组某一个索引出发交替跳高和跳低（奇偶跳），如果可以跳到末尾，则计数器加一，最终返回计数器的值。
+
+这种题目一般都是倒着思考比较容易。因为我虽然不知道你**从哪开始**可以跳到最后，但是我知道你一定是在数组末尾**结束的**。
+
+我们先尝试从题目给的例子打开思路。
+
+以题目中的[10,13,12,14,15]为例。最终计入计数器的出发点一定是跳到了 15 上，15 这一步既可以是跳高（奇数跳）过来的，也可以是跳低（偶数跳）过来的。
+
+- 如果是跳高过来的，那么一定是 14，因此只有 14 的下一个**最小的**比其大（或等于）的是 15。
+- 不可能是跳低过来的，因为没有比它大的。而如果前面有比它的，那一定是找一个数 x，x 的下一个**最大**的比其小（或等于）的是 15。
+
+一开始我想到的是单调栈，单很快就发现这行不通。因为题目要求的并不是**下一个**比其大（或等于）的数，而是**下一个最小的**比其大（或等于）。
+
+如果题目要求的是**下一个**比其大（或等于）的数。那么我可以写出如下的代码：
+
+```py
+n = len(A)
+next_higher, next_lower = [-1] * n, [-1] * n
+
+stack = []
+for i, a in enumerate(A):
+    while stack and A[stack[-1]] <= A[i]:
+        next_higher[stack.pop()] = i
+    stack.append(i)
+stack = []
+for i, a in enumerate(A):
+    while stack and A[stack[-1]] >= A[i]:
+        next_lower[stack.pop()] = i
+    stack.append(i)
+```
+
+对上面代码不熟悉的朋友，可以看下我之前写的 [单调栈专题](../thinkings/monotone-stack.md)。
+
+可是我们需要求的是**下一个最小的**比其大（或等于）呀。一种简单的方法是先对 A 进行排序再使用单调栈。比如我们进行升序排序，接下来只要遍历一次排好序的数组，同时结合单调栈即可。 由于已经进行了排序，因为后面的数一定是**不小于**前面的数的，且**对于任意相邻的数 a 和 b，a 的最小的大于等于它本身的数就是 b**，前提是 a 和 b 对应排序之前的索引 i 和 j 满足 i < j。这提示我们排序的时候需要额外记录原始索引。
+
+代码：
+
+```py
+A = sorted([a, i] for i, a in enumerate(A))
+
+```
+
+这里有 1 个细节。即排序的时候如何处理相等情况，比如 a 和 b 相等，是保持之前的相对顺序还是逆序还是都可以？实际上，我们想希望的是保持之前的相对顺序，这样才不会错误相等的情况的解。因此我这里排序的是时候是以 [a, i] 形式保存的数据。
+
+由于除了要处理跳高，我们仍然需要处理跳低。而最关键的是跳低也需要我们**在 a 和 b 相等的情况下，保持之前的相对顺序**。 因此就不能通过简单的排序一次处理。比如我们不能这么干：
+
+```py
+class Solution:
+    def oddEvenJumps(self, A):
+        n = len(A)
+        next_higher, next_lower = [0] * n, [0] * n
+        A = sorted([a, i] for i, a in enumerate(A))
+
+        stack = []
+        for _, i in A:
+            # it means stack[-1]'s next bigger(or equal) is i
+            while stack and stack[-1] < i:
+                next_higher[stack.pop()] = i
+            stack.append(i)
+
+        stack = []
+        for _, i in A[::-1]:
+            # it means stack[-1]'s next smaller(or equal) is i
+            while stack and stack[-1] < i:
+                next_lower[stack.pop()] = i
+            stack.append(i)
+
+        # ...
+```
+
+解决这个问题的方法最简单的莫过于使用两次排序，具体见下方代码区。
+
+## 代码
+
+代码支持： Python3, CPP
+
+```python
+class Solution:
+    def oddEvenJumps(self, A):
+        n = len(A)
+        next_higher, next_lower = [0] * n, [0] * n
+
+        stack = []
+        for _, i in sorted([a, i] for i, a in enumerate(A)):
+            # it means stack[-1]'s next bigger(or equal) is i
+            while stack and stack[-1] < i:
+                next_higher[stack.pop()] = i
+            stack.append(i)
+
+        stack = []
+        for _, i in sorted([-a, i] for i, a in enumerate(A)):
+            # it means stack[-1]'s next smaller(or equal) is i
+            while stack and stack[-1] < i:
+                next_lower[stack.pop()] = i
+            stack.append(i)
+
+        higher, lower = [False] * n, [False] * n
+        higher[-1] = lower[-1] = True
+        ans = 1
+        for i in range(n - 2, -1, -1):
+            higher[i] = lower[next_higher[i]]
+            lower[i] = higher[next_lower[i]]
+            ans += higher[i]
+        return ans
+
+```
+
+**复杂度分析**
+
+令 N 为数组 A 的长度。
+
+- 时间复杂度：$$O(NlogN)$$
+- 空间复杂度：$$O(N)$$
+
+更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
+
+关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
+
+![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu0yircgj30p00dwt9t.jpg)
