Processing math: 100%
2 Star 2 Fork 1

Krum/leetcode

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
.github
.vscode
91
assets
backlog
collections
daily
problems
1.two-sum.en.md
1.two-sum.md
100.same-tree.md
1004.max-consecutive-ones-iii.md
101.symmetric-tree.md
1011.capacity-to-ship-packages-within-d-days-en.md
1011.capacity-to-ship-packages-within-d-days.md
1014.best-sightseeing-pair.md
1015.smallest-integer-divisible-by-k.md
1019.next-greater-node-in-linked-list.md
102.binary-tree-level-order-traversal.md
1020.number-of-enclaves.md
1023.camelcase-matching.md
103.binary-tree-zigzag-level-order-traversal.md
1031.maximum-sum-of-two-non-overlapping-subarrays.md
1032.stream-of-characters.md
104.maximum-depth-of-binary-tree.md
108.convert-sorted-array-to-binary-search-tree.md
109.Convert-Sorted-List-to-Binary-Search-Tree.md
11.container-with-most-water.md
1104.path-in-zigzag-labelled-binary-tree.md
1128.number-of-equivalent-domino-pairs.md
113.path-sum-ii.md
1131.maximum-of-absolute-value-expression.md
1168.optimize-water-distribution-in-a-village-en.md
1168.optimize-water-distribution-in-a-village.md
1186.maximum-subarray-sum-with-one-deletion.md
1203.sort-items-by-groups-respecting-dependencies.md
121.best-time-to-buy-and-sell-stock.md
1218.longest-arithmetic-subsequence-of-given-difference.md
122.best-time-to-buy-and-sell-stock-ii.md
1227.airplane-seat-assignment-probability.md
124.binary-tree-maximum-path-sum.md
125.valid-palindrome.md
1255.maximum-score-words-formed-by-letters.md
1260.shift-2d-grid.md
1261.find-elements-in-a-contaminated-binary-tree.md
1262.greatest-sum-divisible-by-three.md
128.longest-consecutive-sequence.md
129.sum-root-to-leaf-numbers.md
1297.maximum-number-of-occurrences-of-a-substring.md
130.surrounded-regions.md
131.palindrome-partitioning.md
1310.xor-queries-of-a-subarray.md
1332.remove-palindromic-subsequences.md
1334.find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md
136.single-number.md
1371.find-the-longest-substring-containing-vowels-in-even-counts.en.md
1371.find-the-longest-substring-containing-vowels-in-even-counts.md
1381.design-a-stack-with-increment-operation.md
139.word-break.md
140.word-break-ii.md
142.Linked-List-Cycle-II.md
1435.jump-game-iv.md
1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit.md
144.binary-tree-preorder-traversal.md
1449.form-largest-integer-with-digits-that-add-up-to-target.md
145.binary-tree-postorder-traversal.md
146.lru-cache.md
147.insertion-sort-list.md
1494.parallel-courses-ii.md
15.3sum.md
150.evaluate-reverse-polish-notation.md
152.maximum-product-subarray.md
1521.find-a-value-of-a-mysterious-function-closest-to-target.md
1526.minimum-number-of-increments-on-subarrays-to-form-a-target-array.md
155.min-stack.md
1558.minimum-numbers-of-function-calls-to-make-target-array.md
1574.shortest-subarray-to-be-removed-to-make-array-sorted.md
160.Intersection-of-Two-Linked-Lists.md
1631.path-with-minimum-effort.md
1649.create-sorted-array-through-instructions.md
1658.minimum-operations-to-reduce-x-to-zero.md
167.two-sum-ii-input-array-is-sorted.md
1671.minimum-number-of-removals-to-make-mountain-array.md
169.majority-element.md
1697.checking-existence-of-edge-length-limited-paths.md
17.Letter-Combinations-of-a-Phone-Number.md
172.factorial-trailing-zeroes.md
1737.change-minimum-characters-to-satisfy-one-of-three-conditions.md
19.removeNthNodeFromEndofList.md
190.reverse-bits.md
191.number-of-1-bits.md
198.house-robber.en.md
198.house-robber.md
199.binary-tree-right-side-view.md
2.add-two-numbers.en.md
2.add-two-numbers.md
20.valid-parentheses.md
200.number-of-islands.md
201.bitwise-and-of-numbers-range.md
203.remove-linked-list-elements.md
206.reverse-linked-list.md
208.implement-trie-prefix-tree.md
209.minimum-size-subarray-sum.md
21.merge-two-sorted-lists.md
211.add-and-search-word-data-structure-design.md
212.word-search-ii.md
215.kth-largest-element-in-an-array.md
219.contains-duplicate-ii.md
22.generate-parentheses.md
221.maximal-square.md
226.invert-binary-tree.md
227.basic-calculator-ii.md
229.majority-element-ii.md
23.merge-k-sorted-lists.md
230.kth-smallest-element-in-a-bst.md
232.implement-queue-using-stacks.md
236.lowest-common-ancestor-of-a-binary-tree.md
238.product-of-array-except-self.md
239.sliding-window-maximum.md
24.swapNodesInPairs.md
240.search-a-2-d-matrix-ii.md
25.reverse-nodes-in-k-groups-en.md
25.reverse-nodes-in-k-groups.md
26.remove-duplicates-from-sorted-array.md
263.ugly-number.md
279.perfect-squares.md
283.move-zeroes.md
29.divide-two-integers.md
295.find-median-from-data-stream.md
297.serialize-and-deserialize-binary-tree.md
3.longest-substring-without-repeating-characters.md
30.substring-with-concatenation-of-all-words.md
301.remove-invalid-parentheses.md
309.best-time-to-buy-and-sell-stock-with-cooldown.md
31.next-permutation.md
312.burst-balloons.md
32.longest-valid-parentheses.md
322.coin-change.md
328.odd-even-linked-list.md
33.search-in-rotated-sorted-array.md
330.patching-array.md
334.increasing-triplet-subsequence.md
335.self-crossing.md
337.house-robber-iii.md
342.power-of-four.md
343.integer-break.md
349.intersection-of-two-arrays.md
365.water-and-jug-problem.md
371.sum-of-two-integers.md
378.kth-smallest-element-in-a-sorted-matrix.md
380.insert-delete-getrandom-o1.md
39.combination-sum.md
394.decode-string.md
4.median-of-two-sorted-arrays.md
40.combination-sum-ii.md
401.binary-watch.md
416.partition-equal-subset-sum.md
42.trapping-rain-water.en.md
42.trapping-rain-water.md
424.longest-repeating-character-replacement.md
437.path-sum-iii.md
445.add-two-numbers-ii.md
454.4-Sum-ii.en.md
454.4-sum-ii.md
455.AssignCookies.md
46.permutations.md
460.lfu-cache.md
464.can-i-win.md
47.permutations-ii.md
472.concatenated-words.md
474.ones-and-zeros-en.md
48.rotate-image.md
480.sliding-window-median.md
483.smallest-good-base.md
488.zuma-game.md
49.group-anagrams.md
493.reverse-pairs.md
494.target-sum.md
5.longest-palindromic-substring.md
50.pow-x-n.md
501.Find-Mode-in-Binary-Search-Tree-en.md
513.find-bottom-left-tree-value.md
516.longest-palindromic-subsequence.md
518.coin-change-2.md
52.N-Queens-II.md
53.maximum-sum-subarray-cn.md
53.maximum-sum-subarray-en.md
547.friend-circles-en.md
547.friend-circles.md
55.jump-game.md
56.merge-intervals.md
560.subarray-sum-equals-k.en.md
560.subarray-sum-equals-k.md
5640.maximum-xor-with-an-element-from-array.md
57.insert-interval.md
575.distribute-candies.md
60.permutation-sequence.md
609.find-duplicate-file-in-system.md
61.Rotate-List.md
611.valid-triangle-number.md
62.unique-paths.md
63.unique-paths-ii.md
66.plus-one.md
665.non-decreasing-array.md
673.number-of-longest-increasing-subsequence.md
679.24-game.md
686.repeated-string-match.md
715.range-module.md
718.maximum-length-of-repeated-subarray.md
721.accounts-merge.md
73.set-matrix-zeroes.md
75.sort-colors.md
754.reach-a-number.md
768.max-chunks-to-make-sorted-ii.md
78.subsets-en.md
78.subsets.md
785.is-graph-bipartite.md
79.word-search-en.md
79.word-search.md
790.domino-and-tromino-tiling.md
799.champagne-tower.md
80.remove-duplicates-from-sorted-array-ii.md
801.minimum-swaps-to-make-sequences-increasing.md
805.split-array-with-same-average.md
816.ambiguous-coordinates.md
820.short-encoding-of-words.md
821.shortest-distance-to-a-character.md
839.similar-string-groups.md
84.largest-rectangle-in-histogram.md
85.maximal-rectangle.md
86.partition-list.md
874.walking-robot-simulation.md
875.koko-eating-bananas.md
877.stone-game.md
88.merge-sorted-array.md
886.possible-bipartition.md
887.super-egg-drop.md
895.maximum-frequency-stack.md
898.bitwise-ors-of-subarrays.md
90.subsets-ii-en.md
90.subsets-ii.md
900.rle-iterator.md
91.decode-ways.md
911.online-election.md
912.sort-an-array.md
92.reverse-linked-list-ii.md
932.beautiful-array.md
935.knight-dialer.md
94.binary-tree-inorder-traversal.md
947.most-stones-removed-with-same-row-or-column.md
95.unique-binary-search-trees-ii.md
959.regions-cut-by-slashes.md
96.unique-binary-search-trees.md
975.odd-even-jump.md
978.longest-turbulent-subarray.md
98.validate-binary-search-tree.md
987.vertical-order-traversal-of-a-binary-tree.md
995.minimum-number-of-k-consecutive-bit-flips.md
Number-Stream-to-Intervals.md
binode-lcci.md
get-kth-magic-number-lcci.md
lcp20.meChtZ.md
max-black-square-lcci.md
selected
templates
thinkings
todo/candidates
.gitignore
CONTRIBUTING.en.md
CONTRIBUTING.md
Kapture 2020-08-19 at 11.37.36.gif
LICENSE.txt
README.en.md
README.md
SUMMARY.md
book.json
cover.jpg
donation.md
epilogue.md
introduction.md
package.json
thanksGiving.md
thanksGiving2.md
thanksGiving3.md
克隆/下载
975.odd-even-jump.md 9.55 KB
一键复制 编辑 原始数据 按行查看 历史
lucifer 提交于 4年前 . fix: $$ -> $

题目地址 (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

前置知识

公司

  • 暂无

思路

题目要求我们从数组某一个索引出发交替跳高和跳低(奇偶跳),如果可以跳到末尾,则计数器加一,最终返回计数器的值。

这种题目一般都是倒着思考比较容易。因为我虽然不知道你从哪开始可以跳到最后,但是我知道最终被计算进返回值的一定是在数组末尾结束的

我们先尝试从题目给的例子打开思路。

以题目中的[10,13,12,14,15]为例。最终计入计数器的出发点一定是跳到了 15 上,15 这一步既可以是跳高(奇数跳)过来的,也可以是跳低(偶数跳)过来的。

  • 如果是跳高过来的,那么一定是 14,因此只有 14 的下一个最小的比其大(或等于)的是 15。
  • 不可能是跳低过来的,因为没有比它大的。而如果前面有比它大的,那一定是找一个数 x,x 的下一个最大的比其小(或等于)的是 15。

一开始我想到的是单调栈,单很快就发现这行不通。因为题目要求的并不是下一个比其大(或等于)的数,而是下一个最小的比其大(或等于)。

如果题目要求的是下一个比其大(或等于)的数。那么我可以写出如下的代码:

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)

对上面代码不熟悉的朋友,可以看下我之前写的 单调栈专题

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

代码:

A = sorted([a, i] for i, a in enumerate(A))

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

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

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)

        # ...

解决这个问题的方法最简单的莫过于使用两次排序,具体见下方代码区。

现在已经有了两个数组,这两个数组可以帮助我们

  • 快速找到下一个最小的比其大(或等于)的数。(奇数跳)
  • 快速找到下一个最大的比其小(或等于)的数。(偶数跳)

数据已经预处理完毕。接下来,只需要从结果倒推即可。这提示我们从后往前遍历。

算法:

  • 使用前面的方法预处理出 next_higher 和 next_lower
  • 使用两个数组 higher 和 lower。higher[i] 表示是否可从 i 开始通过跳高的方式奇偶跳到达数组最后一项,lower 也是类似。
  • 从后往前倒推遍历。如果 lower[next_higher[i]] 为 true 说明 i 是可以通过跳高的方式奇偶跳到达数组最后一项的。higher[next_lower[i]] 也是类似。
  • 最后返回 higher 中 为 true 的个数。

代码

代码支持: Python3

Python Code:

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)

有的同学好奇为什么不考虑 lower。类似:

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] or lower[i]
return ans

根本原因是题目要求我们必须从奇数跳开始,而不是能偶数跳开始。如果题目不限制奇数跳和偶数跳,你可以自己自由选择的话,就必须使用上面的代码啦。

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/Krum/leetcode.git
git@gitee.com:Krum/leetcode.git
Krum
leetcode
leetcode
master

搜索帮助