免费建站模板,横栏网站建设,上海网站关键排名,spring做网站题目
852. 山脉数组的峰顶索引 - 力扣#xff08;LeetCode#xff09;
思路
使用二分查找来定位峰顶
对于中间元素#xff0c;比较它与其右侧元素的大小#xff1a;
如果 arr[mid] arr[mid1]#xff0c;说明我们在上坡阶段#xff0c;峰顶在右侧
如果 arr[mid…题目
852. 山脉数组的峰顶索引 - 力扣LeetCode
思路
使用二分查找来定位峰顶
对于中间元素比较它与其右侧元素的大小
如果 arr[mid] arr[mid1]说明我们在上坡阶段峰顶在右侧
如果 arr[mid] arr[mid1]说明我们在下坡阶段峰顶在左侧或当前位置
不断缩小搜索范围直到 left right此时指向的就是峰顶位置
时间复杂度和空间复杂度
时间复杂度O(log n)符合题目要求
空间复杂度O(1)
正确的写法
class Solution {
public:int peakIndexInMountainArray(vectorint arr) {int left 0;int right arr.size()-1;while(left right){int mid left (right-left)/2;if(arr[mid] arr[mid1]){left mid1;}else if(arr[mid] arr[mid1]){right mid;}}return left;}
};
