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种算法实现，以下是这个案例的输出结果：

分析：

显而易见，以上算法的时间复杂度为： $O(logn)$ 。

巴特西

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

最新文章

热门文章