欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 162 :Find Peak Element

程序员文章站 2022-03-14 22:52:45
...

问题描述

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.

思路

二分
LeetCode 162 :Find Peak Element

java实现

class Solution {
    public int findPeakElement(int[] nums) {
        if( nums==null || nums.length==0)
            return 0;
        int start=0;
        int end=nums.length-1;
        while (start+1<end){
            int mid=start+(end-start)/2;
            if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1])//是峰值
                return mid;
            else if(nums[mid]<nums[mid-1] && nums[mid]<nums[mid+1])//是低谷值,左右两侧一点还有峰值,因为题目说是先上升后下降
                start=mid;
            else if(nums[mid]<nums[mid+1])//位于上升区间 mid以后半部分肯定有下降,存在峰值
                start=mid;
            else if(nums[mid]>nums[mid+1])//位于下降区间 mid以前半部分肯定有上升,存在峰值
                end=mid;
        }
        if (nums[start]>nums[end])
            return start;
        else
            return end;
    }
}
相关标签: LeetCode 二分法