题目

我们把符合下列属性的数组 A 称作山脉：

A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。

示例 1：

1 2	输入：[0,1,0] 输出：1

示例 2：

1 2	输入：[0,2,1,0] 输出：1

提示：

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A 是如上定义的山脉

Let’s call an array A a mountain if the following properties hold:

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

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

1 2	Input: [0,1,0] Output: 1

Example 2:

1 2	Input: [0,2,1,0] Output: 1

Note:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain, as defined above.

解题方法

循环遍历

一次循环遍历，找到第一个大于后面元素的元素索引，循环到末尾仍没有找到，则说明最后一个元素是最大值，返回尾节点索引。这段代码跑了1ms，超过了95.32%的Java提交。

public class Solution {
    // Method 1 1ms 95.32%
    public int peakIndexInMountainArray(int[] A) {
        for (int i = 0; i < A.length - 1; i++) {
            if(A[i] > A[i + 1]) {
                return i;
            }
        }
        return A.length-1;
    }
}

二分查找

使用二分查找，找到比左边大，同时比右边大的元素，返回其索引，当mid值更新为0或者A.length - 1时，直接返回mid值。这段代码跑了0ms，超过了100%的Java提交。

public class Solution {
    // Method 2 0ms 100%
    public int peakIndexInMountainArray(int[] A) {
        int left = 0;
        int right = A.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] > A[mid - 1] && A[mid + 1] > A[mid]) {
                left = mid + 1;
                if (left == A.length - 1) {
                    return left;
                }
            } else if (A[mid] < A[mid - 1] && A[mid + 1] < A[mid]) {
                right = mid - 1;
                if (right == 0) {
                    return right;
                }
            } else {
                return mid;
            }
        }
        return -1;
    }
}