来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/B1IidL
符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 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
示例 3：
输入：arr = [0,10,5,2]
输出：1
示例 4：
输入：arr = [3,4,5,1]
输出：2
示例 5：
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2
提示：
3 <= arr.length <= 104
0 <= arr[i] <= 106
题目数据保证 arr 是一个山脉数组
进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？
解法- 方法1：使用python自带函数找到max及index
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
return arr.index(max(arr))
-
方法2：循环遍历，判别条件即可, 第一个满足 arr[i] > arr[i+1]的下标
-
python
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
n = len(arr)
for i in range(n):
if arr[i] > arr[i+1]:
return i
- c++
class Solution {
public:
int peakIndexInMountainArray(vector& arr) {
int n = arr.size();
int ans = -1;
for(int i=1; i arr[i + 1]) {
ans = i;
break;
}
}
return ans;
}
};
- 方法3： 看到复杂度O(logn) 表示应该用二分法，这题大致满足二分法的条件，左右是顺序的。
- 峰顶的左边满足从小到大
- 峰顶的右边满足从大到小
- 如果中间值比左边值大，表明位于峰顶的左边，改变left
- 如果中间值比右边大，表明位于峰顶的右边，改变right
- python
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
n = len(arr)
left = 0
right = n-1
while left <= right:
mid = left + (right-left) // 2
if arr[mid] > arr[mid+1]:
ans = mid # 表明mid是在上升点，暂时设置为顶点
right = mid - 1
else:
left = mid + 1
return ans
- c++
class Solution {
public:
int peakIndexInMountainArray(vector& arr) {
int n = arr.size();
int left = 0;
int right = n-1;
int ans = -1;
while(left <= right)
{
int mid = (right+left) / 2;
if (arr[mid] > arr[mid+1])
{
right = mid - 1;
ans = mid;
}
else
left = mid + 1;
}
return ans;
}
};
复杂度分析
-
时间复杂度：O(n) O(logn)
-
空间复杂度：O(1)
