
问题
我们把符合下列属性的数组 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
分析:
显而易见,以上算法的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4003。