牛客网面试必刷：BM19 寻找峰值

梦里梦外; 2024-03-22 16:16 20阅读 0赞

#### 牛客网面试必刷：BM19 寻找峰值 ####

*  前言
 *  一、解法1：暴力依次搜索
 *  二、解法2：二分搜索

--------------------

## 前言 ##

**给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。**

**定义：  
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于  
2.假设 nums\[-1\] = nums\[n\] = −∞  
3.对于所有有效的 i 都有 nums\[i\] != nums\[i + 1\]**

--------------------

## 一、解法1：暴力依次搜索 ##

**解题思路：从数组的第一个位置开始，依次与其相邻值进行比较，找到满足nums\[ i \] > nums\[ i + 1\] && nums\[ i \] > nums\[i - 1\] 的。**

需要注意的点有：  
1.nums\[-1\] = nums\[n\] = −∞  
2.当 nums.length = 1 的时候，直接return 0；  
**3.当 i = 0 的时候，只需 nums\[ i \] > nums\[ i + 1\]；当 i = nums.length - 1 的时候，只需 nums\[ i \] > nums\[ i - 1\]，否则会产生索引越界的问题。**

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param nums int整型一维数组 
         * @return int整型
         */
        public int findPeakElement (int[] nums) {
        
            // write code here
            int i = 0;
            if(nums.length == 1) return 0; 
            for(i = 0; i < nums.length; i++){
        
                if(i == 0) {
        
                    if(nums[i] > nums[i+1])
                    return i;
                }else if(i == nums.length - 1){
        
                    if(nums[i] > nums[i - 1])
                    return i;
                }else if(nums[i] > nums[i - 1] && nums[i] > nums[i+1]){
        
                    return i;
                }
            }
            return 0;
        }
    }

这种方法是最简单最暴力的，但是缺点也很明显，就是当峰值出现在数组靠后的位置的时候，搜索的时间可能会很长。

时间复杂度：O（n）  
空间复杂度：O（1）

## 二、解法2：二分搜索 ##

在这里引用二分搜索，可能很多人会有点难以理解，因为数组中的值是无序的。

对于无序的数组，理论上来说是无法使用二分搜索的，因为无序数组无法决定 mid 向 left 方向移动还是向 right 方向移动。

但是这个题目，有一个特别之处：**因为题目将数组边界看成最小值，而我们只需要找到其中一个波峰，因此只要不断地往高处走，一定会有波峰。那我们可以每次找一个标杆元素，将数组分成两个区间，每次就较高的一边走，因此也可以用分治来解决，而标杆元素可以选择区间中点。**

具体做法：

step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。

step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。

step 3：如果中间值小于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。

step 4：最后区间收尾相遇的点一定就是波峰。

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param nums int整型一维数组 
         * @return int整型
         */
        public int findPeakElement (int[] nums) {
        
            // write code here
            int left = 0;
            int right = nums.length - 1;
            while(left < right){
        
                int mid = (right - left)/2 + left;
                if( nums[mid] > nums[mid + 1]){
        
                    right = mid;
                }else{
        
                    left = mid + 1;
                }
            }
            return right;
        }
    }

**需要强调的是，进行二分搜索的时候，条件是 left < right 而不是 left <= right**

**理论上来说，二分搜索的时候 ，left < right 和 left <= right 都是可以的，只需要对应好：left < right 对应 right = mid，left <= right 对应 right = mid - 1；**

但是这一题不一样，因为这题的核心点在于：**如果右边是往下，不一定有坡峰；如果右边是往上，一定能找到波峰**

**如果右边是往下，那 mid 的值可能就是波峰的值，因为 mid 右边的值是往下，如果 mid 左右的值也往下，那 mid 的值就是波峰，所以应该包括把 mid 的值放入到下一次搜索的区间，即 right = mid；**

**同理，如果右边是往上，由于 nums\[n\] = −∞，所以波峰一定存在于 \[mid +1, n\] 中，所以 left = mid +1；**

**这一题应用到了二分搜索的思想，但是也需要结合题目的实际要求进行使用，与常规的二分搜索并不能直接画等号，这里需要特别注意！**

![在这里插入图片描述][0382e45b342b4ff0acb1e10ccd881040.png]

[0382e45b342b4ff0acb1e10ccd881040.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/f0425e1a7b1a4b54a8475b3693ed8ad2.png