find-peak-element

相关阅读：

微信平台：153. Find Minimum in Rotated Sorted Array
简书：153. Find Minimum in Rotated Sorted Array

162. 寻找峰值

1. 描述

峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。

2. 理解

• 元素是否整体有序--no
  不是整体有序无法采用折半查找，直接查找不容易解决
• 可以采用顺序遍历 命中特征是什么？
  峰值元素是指其值大于左右相邻值的元素 这个不是充分条件
  假如是最后一个元素，考虑最后一个元素越界问题。
  假如 相同元素 比较没有作用，顺序遍历需要做很多判断
• 假如数组i 随便一个元素，i-1 必然存在(数组元素大约等于2)
  i+1不确定了

array(i)>array(i-1)

这说明array（i-1）肯定不是peak ，因为还有比他大的
array(i)又可能是

array(i)<array(i-1)

array(i)肯定不是最大值，
array(i-1)又可能是

array(i)==array(i-1)
无法排除了，左右2个都可能出现。
还是根据题目要求寻找peak元素就是最大的。

• 元素相同的时候，还是两两比较。小的肯定不是
  array[begin] <=array[i] array[begin] 肯定不是

array[end] <=array[i] array[end] 肯定不是

• 剩余的元素就是答案 最简单情况 only one

3. 测试

1. 数据相等

   
   image.png

2. 简单数据

   
   image.png
   升序

4. code

c++

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
     
        int begin=0;
        int end =nums.size()-1;
        int mid=0;
        while((end-begin)>1){
            mid=(begin+end)/2;
            
            if (nums[mid]>nums[mid-1]){
                begin=mid;
            }else if(nums[mid]<nums[mid-1]) {
                end=mid-1;
            }else if(nums[mid] ==nums[mid-1]){
                if (nums[mid] >=nums[begin])
                {
                    begin++;
                }
                 
                if (nums[mid] >=nums[end])
                {
                    end--;
                }    
            }
            
        }
        
        return nums[begin]>=nums[end]?begin:end; 
    }
};
执行用时: 4 ms, 在Find Peak Element的C++提交中击败了99.63% 的用户

go

/**
time:nlog(n)
space:o(1)
执行用时: 4 ms, 在Find Peak Element的Go提交中击败了100.00% 的用户
**/
func findPeakElement(nums []int) int {
    start:=0;
    end:=len(nums)-1;
    mid:=0
    //quit
    for (end-start)>1{
        mid=(start+end)/2
        if nums[mid]>nums[mid-1]{
            start=mid//升序特点 array(mid)>array(mid-1)>array(mid-2)
        }else if  nums[mid]<nums[mid-1]{
            end=mid-1; //降序特点 array(mid)<array(mid-1)<array(mid-2)
        }else if   nums[mid]<nums[mid-1]{
            //仍然使用排除法
            if nums[mid]>=nums[start]{
                start=start+1
            }
            if nums[mid]>=nums[end]{
                end=end-1;
            }
        }
        
    }
    
    if nums[start]>=nums[end]{
        return start
    }
    return end
}