【LeetCode每日一题】162.寻找峰值.md

发表于   |   分类于 ，   |   阅读次数

162.寻找峰值

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

示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。

说明:
你的解法应该是 O(logN) 时间复杂度的。

如果一个题目，可以简单到用复杂度O(n)的方式解决，但题目要求复杂度为O(logN)复杂度，这种情况下基本上就直接考虑使用二分查找。

但原始二分查找要求数组是有序的，很显然，这个题目中数组并无序。所以我们要转化一下思路，二分就是折半嘛，如何才能折半查找呢？

对于任何一个数组中的元素，如果它大于右边的元素，那么这个元素肯定处于一个递减区间里，所以对于这个递减区间的峰值，肯定在这个元素的左侧（包括它自己）。

这个性质很隐蔽，但也是解决这个问题的最重要的性质，如果能想明白这个，问题就迎刃而解了。

我们采用折半查找的思想，取中间元素，如果中间元素大于右边元素，那么再比较和左边元素，如果也大于左边，那么它就是峰值元素。如果不大于左边元素，那么说明峰值在它左侧，我们再对它左侧区间进行查找，直到找到峰值即可。

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
func findPeakElement(nums []int) int {
    length := len(nums)
    if length == 1 {
        return 0
    }
    start, end := 0, length-1
    mid := 0
    for start <= end {
        mid = (start + end) / 2
        // 这里由于数组特殊性
        // 如果mid为0，那么还要判断mid位置和mid+1位置的大小
        // 只有nums[mid] >= nums[mid+1]时，位置0才是峰值元素索引
        // 比如nums=[1,2]，mid=0，此时峰值元素为2; nums=[1,1],mid=0，此时峰值元素为1,返回索引0或1均可.
        if (mid == 0 && nums[mid] >= nums[mid+1]) || mid == length-1 {
            return mid
        }
        if nums[mid] < nums[mid+1] {
            start = mid + 1
        } else if nums[mid] > nums[mid-1] {
            return mid
        } else {
            end = mid - 1
        }
    }

    return mid
}