1 问题
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
示例 1：
输入：arr = [0,1,0]
输出：1
示例 2：
输入：arr = [1,3,5,4,2]
输出：2
2 方法
- 循环遍历
题目给的是一个山峰数组，所以是先递增再递减
思路一：
对数组进行遍历，如果遍历到的那个元素比下一个元素大，则这个元素。 - 二分法查找
在山峰数组中，因为是先递增再递减，要使用二分查找方法的话
假设满足题目要求所要得元素下标为mid，那么就满足在下标i<mid时，
这个时候arr[i]<arr[i+1]是一直成立的，相反，在满足下标i>mid时，arr[i]>arr[i+1]也是一直成立的。
这样就有一个思路：
定义左边left=0，右边right=len(arr)-2，ans = 0。
这样定义是防止特殊数组的出现，如只有三个数的数组，这个时候就取中间 。mid = (left+right)/2
如果arr[mid]>arr[mid+1],则定义ans = mid，此时right向左边移动一位，如果arr[mid]<arr[mid+1]，则left向左边移动一位。
代码如下： - 第三种：使用python内部函数
直接使用max(arr)求出最大值，再arr.index(max(arr))直接求出最大值下标。
山峰数组代码
| //循环遍历查找最大值 arr = [12, 26, 48, 49, 56, 79, 50, 44, 32, 11] n = len(arr) ans = 0 for i in range(n): if arr[i] > arr[i + 1]: ans = i break print(ans) //使用二分法查找 arr = [12, 26, 48, 49, 56, 79, 50, 44, 32, 11] n = len(arr) left, right, ans = 1, n - 2, 0 while left <= right: mid = (left + right) // 2 if arr[mid] > arr[mid + 1]: ans = mid right = mid - 1 else: left = mid + 1 print(ans) //使用python内部函数直接求 arr = [12, 26, 48, 49, 56, 79, 50, 44, 32, 11] print(arr.index(max(arr))) |
4 结语
针对山峰数组问题，提出了循环遍历，二分法，python内部函数等方法解决问题，对于二分法要注意的是，每一次进行二分法查找之前，先对定义的指针进行移动。
