ChunNote
0%

leetCode-162:Find Peak Element

发表于 分类于

问题描述

给定一个整形数组，要求找出数组中任意一个 peak元素下标（peak元素定义：比左边和右边的元素值都大）。题目链接：**点我**

样例输入输出

输入：nums = [1,2,3,1]

输出：2

说明：元素 3 比左边元素 2 大，比右边元素 1 大，所以返回其下标 2

输入：nums = [1,2,1,3,5,6,4]

输出：5

说明：元素 6 比左边元素 5 大，比右边元素 4 大，故返回其下标 5。另外，如果返回下标 1 也是正确的，因为元素 2 比左边元素 1 和右边元素 1 都大，所以下标 1 的元素也是一个 peak 元素

问题解法

解法一：遍历

直接使用 for 循环进行遍历查找，找到就直接返回下标。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
    public int findPeakElement(int[] nums)
    {
        if (nums.length <=1 || nums[0] > nums[1])
        {
            return 0;
        }
        
        for (int i = 1; i < nums.length - 1; i++)
        {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
            {
                return i;
            }
        }
                               
        return nums.length - 1;
    }
}

解法二：二分查找

此种解法参考：https://leetcode.com/problems/find-peak-element/solution/。主要是将数组中间元素与相邻元素进行比较，如果中间元素刚好比相邻的元素都大，那么这个元素下标就是要找的值。如果中间元素比左边元素大，说明在当前范围内中间元素呈上升的趋势，所以要找目标值只能在右侧查找，反之，则在左侧进行查找。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution
{
    public int findPeakElement(int[] nums)
    {
        int left = 0;
        int right = nums.length - 1;
        while (left < right)
        {
            int middle = (left + right) / 2;
            if (nums[middle] > nums[middle + 1] && middle > 0 && nums[middle] > nums[middle - 1])
            {
                return middle;
            }
            
            if (nums[middle] > nums[middle + 1])
            {
                right = middle - 1;
            }
            else
            {
                left = middle + 1;
            }
        }
        
        // 只能是 left，不能是 right，因为 [2, 1] 时，right 是 -1
        return left;
    }
}

参考资料

https://leetcode.com/problems/find-peak-element/solution/