寻找峰值

https://www.lintcode.com/problem/75/description?utm_source=sc-libao-ql

描述

给定一个长度为 n 的整数数组 nums，其具有以下特点：

• 相邻位置的数字是不同的

• nums 至少存在一个峰值

假定 P 是峰值的位置则满足 nums[P] > nums[P-1] 且 nums[P] > nums[P+1]，返回数组中任意一个峰值的位置。

• $1≤nums.length≤10001≤nums.length≤1000$

• $−231≤nums[i]≤231−1−231≤nums[i]≤231−1$

• 数组保证至少存在一个峰

• 如果数组存在多个峰，返回其中任意一个就行

• 数组至少包含 3 个数

样例

样例 1：

输入：

A = [1, 2, 1, 3, 4, 5, 7, 6]

输出：

1

解释：

返回任意一个峰顶元素的下标，6也同样正确。 样例 2：

输入：

A = [1,2,3,4,1]

输出：

3

解释：

返回峰顶元素的下标。

挑战

时间复杂度$O(logN)O(logN)$

分析：

• 选择中点： 首先，选择数组的中间位置mid。

• 比较中点与其右邻居：

  • 如果 nums[mid]>nums[mid+1]，说明峰值在中点左边或者中点本身是峰值，因为在这种情况下，左侧肯定有一个上升趋势（包括中点本身）。

  • 如果 nums[mid]<nums[mid+1]，说明峰值在中点右边，因为右侧有一个上升趋势，这意味着峰值必定在右边。

• 缩小搜索范围： 根据上述比较结果，我们可以缩小搜索区间至中点左边或右边，继续用二分法搜索，直到找到一个峰值。

from typing import (
    List,
)

class Solution:
    """
    @param a: An integers array.
    @return: return any of peek positions.
    """
    def find_peak(self, a: List[int]) -> int:
        # write your code here
        start, end = 0, len(a) - 1

        while start + 1 < end:
            mid = (start + end) // 2
            if a[mid-1] < a[mid] > a[mid+1]:
                return mid
            elif a[mid] < a[mid + 1]:
                start = mid 
            else:
                end = mid