題目

難度：★★☆☆☆
類型：數(shù)組

我們把符合下列屬性的數(shù)組 A 稱作山脈：

A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
給定一個確定為山脈的數(shù)組，返回任何滿足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。

提示
3 <= A.length <= 10000
0 <= A[i] <= 10^6
A 是如上定義的山脈

示例

示例 1
輸入：[0,1,0]
輸出：1

示例 2
輸入：[0,2,1,0]
輸出：1

題目

我們使用二分法解決這個問題。

初始化考察的線段的左右端點：left=0，right=len(A)-1；

中點坐標(biāo)：mid = left+(right-left)//2，中點左右相鄰位置的坐標(biāo)midl=mid-1，midr=mid+1；

通過中間處的連續(xù)三個元素查看趨勢，山坡和山頂?shù)膮^(qū)別：

山頂：中間位置元素比相鄰左右元素都大，A[mid] > A[midl]，A[mid]>A[midr]；

山坡：中間及其相鄰左右元素單調(diào)遞增或遞減，A[midl]<A[mid]<A[midr]（左山坡）或者A[midl]>A[mid]>A[midr]（右山坡）

對于左山坡，山頂在右半部分，我們?nèi)サ糇蟀氩糠?，考察右半部分?/p>

對于右山坡，山頂在左半部分，我們?nèi)サ粲野氩糠?，考察左半部分?/p>

class Solution:
    def peakIndexInMountainArray(self, A):
        """
        :param A: List[int]
        :return: int
        """
        left, right = 0, len(A)-1
        while True:
            mid = left + (right - left) // 2
            midl, midr = mid-1, mid+1
            if A[mid] > A[midl] and A[mid] > A[midr]:
                return mid
            elif A[midl] < A[mid] < A[midr]:            # 左側(cè)山坡
                left = mid + 1
            elif A[midl] > A[mid] > A[midr]:            # 右側(cè)山坡
                right = mid - 1

如有疑問或建議，歡迎評論區(qū)留言~