題目

852. 山脈數組的封頂索引

給定一個長度為 n 的整數 山脈 數組 arr ，其中的值遞增到一個 峰值元素 然后遞減。

返回峰值元素的下標。

你必須設計并實現時間復雜度為 O(log(n)) 的解決方案。

示例 1：

輸入：arr = [0,1,0]
輸出：1

示例 2：

輸入：arr = [0,2,1,0]
輸出：1

示例 3：

輸入：arr = [0,10,5,2]
輸出：1

題解

1. 遍歷

class Solution(object):def peakIndexInMountainArray(self, arr):""":type arr: List[int]:rtype: int"""for i in range(1, len(arr) -1):if arr[i] > arr[i + 1]:return ireturn False

2. 二分查找

class Solution(object):def peakIndexInMountainArray(self, arr):""":type arr: List[int]:rtype: int"""# 二分查找n = len(arr)left = 0right = n - 1ans = -1while left <= right:mid = (left + right) // 2if arr[mid] > arr[mid + 1]:ans = midright = mid - 1else:left = mid + 1return ans