题目： https://leetcode-cn.com/problems/odd-even-jump/submissions/ 这道题理解都花了我好久，最后理解出来的题目意思是：从每一位开始，先找到比它大或等于的数里面最小的(相同取前)，然后再找到比它小或等于的数里面最大的(相同取前)，直到找不到为止，如果这时候，停在最后一位，则符合要求 需要问的是，数组内有多少值符合这个要求。 首先最后一位肯定是符合要求的。 思路就是建两个数组，第一个数组保存比它大或等于的数里面最小的(称为A值)，第二个数组保存比它小或等于的数里面最大的(称为B值) 再从后往前依次计算，一个数，如果它的A值是最后一位，那它就是符合要求，如果它没有A值，则不符合要求，如果它的A值的B值符合要求，那它本身也符合 所以每个数最多获取两次值。 最难的就是找到那个A数组和B数组了 我做的就是建一个Node数组，按值排序，找key
代码： public int oddEvenJumps(int[] A) { int len = A.length; Node[] nodes = new Node[len]; for (int i = 0; i < len; i++) { nodes[i] = new Node(i, A[i]); } Arrays.sort(nodes, new Comparator() { @Override public int compare(Node o1, Node o2) { if (o1.val == o2.val) { return o1.key - o2.key; } return o1.val - o2.val; } }); //找到比它大的最小值所在位置数组 int[] biggerMin = new int[len]; for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { if (nodes[j].key > nodes[i].key) { biggerMin[nodes[i].key] = nodes[j].key; break; } } } Arrays.sort(nodes, new Comparator() { @Override public int compare(Node o1, Node o2) { if (o1.val == o2.val) { return o1.key - o2.key; } return o2.val - o1.val; } }); //找到比它小的最大值所在位置数组 int[] minBigest = new int[len]; for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { if (nodes[j].key > nodes[i].key) { minBigest[nodes[i].key] = nodes[j].key; break; } } } int k = 1; boolean[] ans = new boolean[len]; ans[len - 1] = true;//最后一位自然符合 for (int i = len - 2; i >= 0; i–) { int y = biggerMin[i]; if (y == 0) { //没有比它大的，自然就不符合 continue; } //都找到最后一位了，自然符合 if (y == len - 1) { ans[i] = true; k++; continue; } int z = minBigest[y]; //没有更小的，或者找到的更小不符合，那就自然不符合 if (z == 0 || (!ans[z])) { continue; } ans[i] = true; k++; } return k; }
class Node { int key; int val; Node(int key, int val) { this.key = key; this.val = val; } }