Skip to content

Commit 915443b

Browse files
authored
Update 975.odd-even-jump.md
1 parent 8869988 commit 915443b

File tree

1 file changed

+2
-2
lines changed

1 file changed

+2
-2
lines changed

problems/975.odd-even-jump.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -107,7 +107,7 @@ for i, a in enumerate(A):
107107

108108
对上面代码不熟悉的朋友,可以看下我之前写的 [单调栈专题](../thinkings/monotone-stack.md)
109109

110-
可是我们需要求的是**下一个最小的**比其大(或等于)呀。一种简单的方法是先对 A 进行排序再使用单调栈。比如我们进行升序排序,接下来只要遍历一次排好序的数组,同时结合单调栈即可。 由于已经进行了排序,因为后面的数一定是**不小于**前面的数的,且**对于任意相邻的数 a 和 b,a 的最小的大于等于它本身的数就是 b**,前提是 a 和 b 对应排序之前的索引 i 和 j 满足 i < j。这提示我们排序的时候需要额外记录原始索引。
110+
可是我们需要求的是**下一个最小的**比其大(或等于)呀。一种简单的方法是先对 A 进行排序再使用单调栈。比如我们进行升序排序,接下来只要遍历一次排好序的数组,同时结合单调栈即可。 由于已经进行了排序,因此后面的数一定是**不小于**前面的数的,且**对于任意相邻的数 a 和 b,a 的最小的大于等于它本身的数就是 b**,前提是 a 和 b 对应排序之前的索引 i 和 j 满足 i < j。这提示我们排序的时候需要额外记录原始索引。
111111

112112
代码:
113113

@@ -116,7 +116,7 @@ A = sorted([a, i] for i, a in enumerate(A))
116116

117117
```
118118

119-
这里有 1 个细节。即排序的时候如何处理相等情况,比如 a 和 b 相等,是保持之前的相对顺序还是逆序还是都可以?实际上,我们想希望的是保持之前的相对顺序,这样才不会错误相等的情况的解。因此我这里排序的是时候是以 [a, i] 形式保存的数据。
119+
这里有 1 个细节。即排序的时候如何处理相等情况,比如 a 和 b 相等,是保持之前的相对顺序还是逆序还是都可以?实际上,我们想希望的是保持之前的相对顺序,这样才不会错过相等的情况的解。因此我这里排序的是时候是以 [a, i] 形式保存的数据。
120120

121121
由于除了要处理跳高,我们仍然需要处理跳低。而最关键的是跳低也需要我们**在 a 和 b 相等的情况下,保持之前的相对顺序**。 因此就不能通过简单的排序一次处理。比如我们不能这么干:
122122

0 commit comments

Comments
 (0)