C#LeetCode刷题之#852-山脉数组的峰顶索引（Peak Index in a Mountain Array）

问题

我们把符合下列属性的数组 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 的值。

输入：[0,1,0]

输出：1

输入：[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].

Input: [0,1,0]

Output: 1

Input: [0,2,1,0]

Output: 1

Note:

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

示例

public class Program {

    public static void Main(string[] args) {
        var A = new int[] { 24, 69, 100, 99, 79, 78, 67, 36, 26, 19 };

        var res = PeakIndexInMountainArray(A);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int PeakIndexInMountainArray(int[] A) {
        //二分法
        var low = 1;
        var high = A.Length - 2;
        var mid = 0;
        while(low <= high) {
            mid = low + (high - low) / 2;
            var top = Position(A, mid);
            if(top == 1) {
                high = mid - 1;
            } else if(top == -1) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    private static int Position(int[] A, int index) {
        //-1，index在峰顶左边
        //1，index在峰顶右边
        //0，index是峰顶
        if(A[index] > A[index - 1] && A[index + 1] > A[index]) return -1;
        if(A[index + 1] < A[index] && A[index] < A[index - 1]) return 1;
        return 0;
    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

2

分析：

显而易见，以上算法的时间复杂度为：  。