class Solution {
public:
int oddEvenJumps(vector<int>& arr) {
}
};
975. 奇偶跳
给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。
你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：
j，使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。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 <= 200000 <= A[i] < 100000原站题解
golang 解法, 执行用时: 364 ms, 内存消耗: 6.9 MB, 提交时间: 2023-09-25 11:22:22
type Node struct {
val int
idx int
}
func oddEvenJumps(A []int) int {
n := make([]Node, len(A))
for i := 0; i < len(A); i++ {
n[i] = Node{A[i], i}
}
sort.Slice(n, func(i, j int) bool {
if n[i].val == n[j].val {
return n[i].idx < n[j].idx
}
return n[i].val < n[j].val
})
ret := 0
odd, even := make(map[int]bool), make(map[int]bool)
for i := 0; i < len(n); i++ {
if success, ok := odd[i]; ok {
if success {
ret++
}
continue
}
if jump(i, 1, n, odd, even) {
ret++
}
}
return ret
}
func jump(idx, flag int, n []Node, odd, even map[int]bool) bool {
if idx >= len(n) {
return false
}
if n[idx].idx == len(n)-1 {
return true
}
if flag%2 == 1 {
if ret, ok := odd[idx]; ok {
return ret
}
for i := idx + 1; i < len(n); i++ {
if n[i].idx < n[idx].idx {
continue
}
odd[idx] = jump(i, flag+1, n, odd, even)
return odd[idx]
}
odd[idx] = false
return odd[idx]
} else {
if ret, ok := even[idx]; ok {
return ret
}
for i := idx + 1; i < len(n); i++ {
if n[i].val == n[idx].val {
even[idx] = jump(i, flag+1, n, odd, even)
return even[idx]
}
}
for i := idx - 1; i >= 0; i-- {
if n[i].idx < n[idx].idx {
continue
}
for j := i - 1; j >= 0; j-- {
if n[j].idx < n[idx].idx {
continue
}
if n[j].val != n[i].val {
break
}
i = j
}
even[idx] = jump(i, flag+1, n, odd, even)
return even[idx]
}
even[idx] = false
return even[idx]
}
return false
}
cpp 解法, 执行用时: 108 ms, 内存消耗: 18.8 MB, 提交时间: 2023-09-25 11:21:20
const int N = 2e4 + 7;
class Solution {
public:
int next_odd[N];// 每一个位置奇数跳的下一个位置
int next_even[N];// 每一个位置偶数跳的下一个位置
// 可以用排序 + 优先队列来初始化 next_odd[] 和 next_even[]
bool dp[N][2];
// dp[i][0] -> 从该位置奇数跳能否到终点
// dp[i][1] -> 从该位置偶数跳能否到终点
int h[N];
int n;
int oddEvenJumps(vector<int>& arr) {
n = arr.size();
for(int i = 0;i < n;i ++) h[i] = i;
// 初始化 next_odd[]
sort(h,h + n,[&](int& a,int& b) {
if(arr[a] == arr[b]) return a < b;
return arr[a] < arr[b];
});
priority_queue<int,vector<int>,greater<int>> q;
for(int i = 0;i < n;i ++) {
// 把数字从小到大枚举
while(!q.empty() && q.top() < h[i]) next_odd[q.top()] = h[i] , q.pop();
q.push(h[i]);
}
while(!q.empty()) next_odd[q.top()] = -1 , q.pop();
// 初始化 next_even[]
sort(h,h + n,[&](int& a,int& b) {
if(arr[a] == arr[b]) return a < b;
return arr[a] > arr[b];
});
for(int i = 0;i < n;i ++) {
// 把数字从小到大枚举
while(!q.empty() && q.top() < h[i]) next_even[q.top()] = h[i] , q.pop();
q.push(h[i]);
}
while(!q.empty()) next_even[q.top()] = -1 , q.pop();
// 然后对每一个位置进行判断
int res = 0;
dp[n - 1][0] = dp[n - 1][1] = true;
res = 1;
for(int i = n - 2;i >= 0;i --) {
dp[i][0] = dp[i][1] = false;
int next = next_odd[i];// 从该点奇数跳
if(next != -1 && dp[next][1]) res ++ , dp[i][0] = true;
next = next_even[i];
if(next != -1 && dp[next][0]) dp[i][1] = true;
}
return res;
}
};
python3 解法, 执行用时: 120 ms, 内存消耗: 19.5 MB, 提交时间: 2023-09-25 11:20:41
class Solution:
# 单调栈
def oddEvenJumps(self, A: List[int]) -> int:
N = len(A)
def make(B: List[int]) -> int:
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 range(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)
java 解法, 执行用时: 108 ms, 内存消耗: 42.8 MB, 提交时间: 2023-09-25 11:19:43
class Solution {
// tree map
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;
}
}