BM19 寻找峰值

分手后的思念是犯贱 2023-10-04 17:40 59阅读 0赞

### 描述 ###

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

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums\[-1\] = nums\[n\] = −∞

3.对于所有有效的 i 都有 nums\[i\] != nums\[i + 1\]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

数据范围：

1≤nums.length≤2×10^5

−2^31<=nums\[i\]<=2^31−1

如输入\[2,4,1,2,7,8,4\]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

![0fdf43d4296438a1153c2c55275dce38.png][]

### 示例1 ###

输入：

[2,4,1,2,7,8,4]

返回值：

说明：

4和8都是峰值元素，返回4的索引1或者8的索引5都可以

### 示例2 ###

输入：

[1,2,3,1]

返回值：

说明：

3 是峰值元素，返回其索引 2

## 方法一（暴力遍历） ##

时间复杂度o(n)

空间复杂度o(1)

/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param numsLen int nums数组长度
     * @return int整型
     *
     * C语言声明定义全局变量请加上static，防止重复定义
     */
    int find(int*nums,int start){
        int end=start+2;
        if(nums[start]<nums[start+1]&&nums[start+1]>nums[end]){
            return start+1;
        }
        else{
            return -1;
        }
    }
    int findPeakElement(int* nums, int numsLen ) {
        // write code here
        
        if(numsLen==2){   //数组中只有两个值
            if(nums[0]>nums[1])
                return 0;
            else
                return 1;
        }
        if(numsLen==1){   //数组只有一个值时
            return 0;
        }
        else{
            if(nums[0]>nums[1]){   //处理第一个值
                return 0;
            }
            for(int i=0;i<numsLen-3;i++){
                int index=find(nums,i);  //三个为一组进行比较
                if(index!=-1){
                    return index;
                }
            }
            if(nums[numsLen-1]>nums[numsLen-2]){    //处理倒数第一个值
                return numsLen-1;
            }
        }
         return -1;
        /*
        //两个端点值是-∞（且元素不重复），我只需要一直找最大的值，那么这个值一定是波峰
        int idx=0;
        for(int i=1;i<numsLen;i++){
            if(nums[i]>nums[idx]){
                idx=i;
            }
        }
        return idx;
        */
    }

**或者寻找数组最大值**

**原因：两个端点值是-∞（且元素不重复），我只需要一直找最大的值，那么这个值一定是波峰**

/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param numsLen int nums数组长度
     * @return int整型
     *
     * C语言声明定义全局变量请加上static，防止重复定义
     */
    
    int findPeakElement(int* nums, int numsLen ) {
        // write code here
        //两个端点值是-∞（且元素不重复），我只需要一直找最大的值，那么这个值一定是波峰
        int idx=0;
        for(int i=1;i<numsLen;i++){
            if(nums[i]>nums[idx]){
                idx=i;
            }
        }
        return idx;
    }

## 方法二：（二分法） ##

时间复杂度o(logn),空间复杂度o(1)

**思想:上坡一定有波峰，下坡不一定有波峰**

import java.util.*;
    
    
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param nums int整型一维数组 
         * @return int整型
         */
    
        //二分法，
        int find(int[] nums,int l,int r){
            while(r>l){
                 int mid=(l+r)/2;
                if(nums[mid]>nums[mid+1])
                    //mid右边是下坡
                    r=mid;
                else{  //mid右边是上坡
                    l=mid+1;
                }
            }
            return r;
        }
        public int findPeakElement (int[] nums) {
            // write code here
            int len=nums.length;
            if(len==1||nums[0]>nums[1]){
                return 0;
            }
            if(nums[len-1]>nums[len-2]){
                return len-1;
            }
            int index=find(nums,0,len-1);  //二分法
            return index;
        }
    }

[0fdf43d4296438a1153c2c55275dce38.png]: https://img-blog.csdnimg.cn/img_convert/0fdf43d4296438a1153c2c55275dce38.png