一个数组先升序再降序，用最优时间复杂度，求最大值？例如[1,2,2,2,2,3,1]

Question

一个数组先升序再降序，求最大值？例如[1,2,2,2,2,3,1]，用最优时间复杂度，算法实现获取最大值3

Answer 1

两种方案吧第一种遍历一次，找到开始变小的那个i，a[i-1]就是最大值，复杂度O(n);第二种，二分法，先去中间的三个值，判断这三个值是否单调，如果不是单调，中间那个就是最大值，否则根据单调方向，找到下一段数组进行二分查找。复杂度O(logn)