[LeetCode] 1095. Find in Mountain Array

[grandyang]

(This problem is an interactive problem.)

You may recall that an array A is a  mountain array  if and only if:

• A.length >= 3
• There exists some i with 0 < i < A.length - 1 such that:
  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[A.length - 1]

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target.  If such an index doesn't exist, return -1.

You can't access the mountain array directly.  You may only access the array using a MountainArray interface:

• MountainArray.get(k) returns the element of the array at index k (0-indexed).
• MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged  Wrong Answer.  Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

Example 2:

Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in `the array,` so we return -1.

Constraints:

• 3 <= mountain_arr.length() <= 10000
• 0 <= target <= 10^9
• 0 <= mountain_arr.get(index) <= 10^9

这道题给了一个山形数组 Mountain Array，关于山形数组的题目，之前也出现过，比如 Longest Mountain in Array 和 Peak Index in a Mountain Array。所谓的山形数组，就是先上升后下降的数组，注意这里是严格的上升和下降。题目中说这个山形数组不能直接访问元素，而是需要调用 get()，数组的长度需要调用 length()，要求尽可能的少调用这些函数，而且还说了假如调用了超过了 100 次的 get 函数，OJ 会自动判为错的解法。这完全是断了直接遍历一遍数组的这条路啊，毕竟这是一道 Hard 题，要给予足够的尊重才行。既然不能暴力搜索，更高效的搜索方法可以用二分搜索，但前提条件是数组必须是有序的，这里的数组是先上升再下降的，没法直接用二分搜索来找目标值。不过假如我们能够将上升和下降的部分分割开来，就可以分别调用二分搜索法啦，临界点就是峰值啦。所以首先要用二分法求个峰值，你可能有个疑问，前面不是说了二分法不能在山形数组中查找目标值吗，怎么这里却可以用来查找峰值呢？嗯，是个好问题，这其实是个特殊情况，一般来说二分法查找的目标值是固定不变的，而这里查找峰值时不是用一个固定的目标值，而是再求出 mid 后，跟其紧挨的下一个位置比较，假如小于下个位置的值，则说明峰值在后面，此时 left 更新为 mid+1，否则 right 更新为 mid，最后的峰值就保存在 left 中。用类似的方法的题目还有 Find Minimum in Rotated Sorted Array。找到了峰值之后，就可以将数组分为两段分别进行二分查找了，这里可以写两个 while 循环分别查找，也可以放到一个子函数中，不过由于前半段是上升的，后半段是下降的，二者的更新方法正好相反，可以用一个 flag 控制一下。最后假如左半段返回是 -1，则返回右半段的结果即可，参见代码如下：

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int n = mountainArr.length(), left = 0, right = n - 1, peak = -1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) left = mid + 1;
            else right = mid;
        }
        peak = left;
        if (mountainArr.get(peak) == target) return peak;
        int idx1 = helper(target, mountainArr, 0, peak - 1, true);
        int idx2 = helper(target, mountainArr, peak + 1, n - 1, false);
        return idx1 == -1 ? idx2 : idx1;
    }
    int helper(int target, MountainArray &mountainArr, int left, int right, bool isAsc) {
        while (left < right) {
            int mid = left + (right - left) / 2, cur = mountainArr.get(mid);
            if (cur == target) return mid;
            else if (cur < target) {
                if (isAsc) left = mid + 1;
                else right = mid;
            } else {
                if (isAsc) right = mid;
                else left = mid + 1;
            }
        }
        return mountainArr.get(right) == target ? right : -1;
    }
};

Github 同步地址:

#1095

类似题目：

Longest Mountain in Array

Peak Index in a Mountain Array

Find Minimum in Rotated Sorted Array

Minimum Number of Removals to Make Mountain Array

参考资料：

https://leetcode.com/problems/find-in-mountain-array/

https://leetcode.com/problems/find-in-mountain-array/discuss/317603/C%2B%2B-Find-Peak-(162)-%2B-Binary-Search

https://leetcode.com/problems/find-in-mountain-array/discuss/317607/JavaC%2B%2BPython-Triple-Binary-Search

LeetCode All in One 题目讲解汇总(持续更新中...)