宜昌建设网站公司,python网站开发实例,河北网站建设有限公司,网站敏感关键词题目#xff1a;162. 寻找峰值 - 力扣#xff08;LeetCode#xff09; 题目描述#xff1a; 题目分析#xff1a; #xff08;1#xff09;据题知#xff0c;索引-1、索引n#xff08;n为数组长度#xff09;处的元素都默认为无穷小#xff0c;我们可以在一开始特判…题目162. 寻找峰值 - 力扣LeetCode 题目描述 题目分析 1据题知索引-1、索引nn为数组长度处的元素都默认为无穷小我们可以在一开始特判一些简单情况当数组长度等于1时直接返回0当索引0处的元素大于索引1处的元素时直接返回0当索引n - 1处的元素大于索引n-2处的元素时返回n - 1。 2如果给定的数组不满足特判条件用折线来描述这个数组的升降一定能找到一个峰值元素如下图所示。 索引0到索引1是上升趋势索引n-2到索引n-1是下降趋势由于数组不存在重复元素所以无论你怎么拼接这条折线中间一定有一个峰值元素。 3假设我们二分到一个元素nums[m]有三种情况1、nums[m]就是峰值元素更新答案退出循环2、nums[m-1] nums[m]这里呈下降趋势而索引0到索引1是上升趋势所以在0 到 m - 1这个区间肯定有一个峰值元素right m - 1往左侧二分3、nums[m1] nums[m]这里呈上升趋势而索引n - 2到索引n - 1是下降趋势所以在m 1 到 n - 2这个区间肯定有一个峰值元素left m 1往右侧二分。 Code
class Solution {public int findPeakElement(int[] nums) {int n nums.length;//数组中只有一个元素直接返回0if(n 1)return 0;//索引0处的元素满足要求返回0if(nums[0] nums[1])return 0;//索引n - 1处的元素满足要求返回n - 1if(nums[n - 1] nums[n - 2])return n - 1;int left 1,right n - 2;int ans 0;while(left right){int m left (right - left) / 2;//nums[m-1] nums[m]这里是下降趋势//那么答案一定在左侧往左侧二分if(nums[m - 1] nums[m]){right m - 1;}//nums[m1] nums[m]这里是上升趋势//答案一定在右侧往右侧二分else if(nums[m 1] nums[m]){left left 1;}else{//nums[m1]和nums[m-1]都不大于nums[m]//那么nums[m]就是峰值元素ans m;break;}}return ans;}
}
