题目在这:https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/
题目分析:
题目一堆数学符号看着难受。给大家解答一下,就是给了一堆数组,其中有一个数X ,这个数的左边和右边的所有数都比他小,所以这个数组叫山脉数组,而这个数X就是山峰。
害,说了这么多不就是找最大值吗?
法一:
巧妙利用库函数解决问题。只需一行代码。
return arr.index(max(arr))
max不用解释了吧,列表里找最大值
index() 方法返回列表中匹配到的第一个数的下标~
法二:
显然可以二分法寻找最大值,毕竟这周二分法周~每日一题全是二分法。
思路分析:
本题和普通二分法有一点区别,就是不知道要找的那个数是什么。
所以需要明确条件。
举个例子:
数组 arr=[1,3,5,4,2] 。显然数组a[0] < a[1] ,山顶点为a[2] = 5.
在山顶点的右边 a[3]>a[4]。
很清晰的得出结论。
当a[i] < a[i+1]时,山顶点在a[i] 的右边。
同理,当a[i] > a[i+1]时,山顶点在a[i] 的左边。
还有一点就是,该山峰数组的山顶,也就是我们要找的那个最大值,一定不在开头和结尾,所以设置left和right的时候记得避开。
上面两点明白了代码就很容易出来了。
l = 1 # 避开开头
r = len(arr) - 2 # 避开结尾
while l < r:
mid = (r+l) // 2
if arr[mid] < arr[mid+1]: # 说明此时 顶点在右边 缩小范围去右边找
l = mid + 1
else: # 此时顶点在左边 缩小范围去左边找
r = mid
return