给定一个整数数组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。（可能存在某些索引，不存在合法的跳跃）
如果从该索引开始，您可以通过跳转一些次数（大于等于0次）到达数组的末尾（索引A.length - 1），那么这是一个有效的起始索引。
返回有效的起始索引的个数。
- <= A.length <= 20000
- 0 <= A[i] < 100000
在线评测地址：lintcode领扣
样例 1:
输入: [10,13,12,14,15]
输出: 2
解析:
从 index 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 是无效的
根据同样的规则，我们可以求出：
存在 3 个有效的起始索引 (i = 1, i = 3, i = 4) 我们可以跳
【题解】
使用Java中的TreeMap用于高效查找当前index之后的相对的最小值和最大值。
定义两个boolean数组记录当前index是否可以奇数跳以及偶数眺到达末尾。
逆推的思维找到有效的起始索引。
public class Solution {
/**
* @param A: An integer array A
* @return: Return the number of good starting indexes
*/
public int oddEvenJumps(int[] A){
int res = 1, lenA = A.length;
// higher[i] = true代表从索引 i 奇数跳可以到达末尾
boolean []higher = new boolean[lenA];
// lower[i] = true代表从索引 i 偶数跳可以到达末尾
boolean []lower = new boolean[lenA];
// 初始化最后一个位置，无论哪种跳法都是已经在末尾了
higher[lenA - 1] = lower[lenA - 1] = true;
// 记录 value - index
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
treeMap.put(A[lenA - 1], lenA - 1);
for (int i = lenA - 2; i >= 0; i--) { // 逆推，分两种情况
// 找到index = i 之后大于等于A[i]的最小的数
Map.Entry high = treeMap.ceilingEntry(A[i]);
// 找到index = i 之后小于等于A[i]的最大的数
Map.Entry low = treeMap.floorEntry(A[i]);
if (high != null){ // 当前位置进行奇数跳取决于目的地的偶数跳是否能到达终点
higher[i] = lower[(int)high.getValue()];
}
if (low != null){ // 同理
lower[i] = higher[(int)low.getValue()];
}
// 起始点一定是奇数跳
if (higher[i]){
res ++;
}
treeMap.put(A[i], i);
}
return res;
}
}
更多语言代码参见：leetcode/lintcode题解
网友评论