leetcode 162 寻找峰值

直观解法1：遍历  算法复杂度O(n)

int findPeakElement(vector<int>& nums) {int size = nums.size();//一个元素，直接返回0if(size == 1) return 0;//两个元素，返回最大的idxif(size == 2) {if(nums[0] > nums[1]) return 0;else return 1;}int max_val = nums[0];int idx = 0; int i = 0;//遍历,同时记录最大值和最大值idxfor(;i + 2 < size - 1; i++){if(nums[i] > max_val){max_val = nums[i];idx = i;}//如果遇到一个波峰，返回idxif(nums[i] < nums[i+1] && nums[i+1] > nums[i+2]) return i+1;}//遍历最后两个，记录最大值的idxif(max_val < nums[i+1]){max_val = nums[i+1];idx = i+1;}if(max_val < nums[i+2]){max_val = nums[i+2];idx = i+2;}//返回最大值的idxreturn idx;}

解法2：题目要求O(logn)，那肯定是二分查找了

int findPeakElement(vector<int>& nums){//单元素，直接返回if(nums.size() == 1) return 0;int l = 0, r = nums.size()-1, mid;while(l < r){mid = (l + r) / 2;// r-l=1的情况if(mid == l) return nums[mid] > nums[r] ? mid : r;if(mid == r) return nums[mid] > nums[l] ? mid : l;//波峰if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1])return mid;if(nums[mid] < nums[mid-1]){r = mid - 1;//这个不能少，我们只需要判断大的一侧就行continue;}if(nums[mid] < nums[mid+1]){l = mid + 1;}}return (l+r)/2;}