Description
An array arr a mountain if the following properties hold:
arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].
You must solve it in O(log(arr.length)) time complexity.
Example 1:
Input: arr = [0,1,0]
Output: 1
Example 2:
Input: arr = [0,2,1,0]
Output: 1
Example 3:
Input: arr = [0,10,5,2]
Output: 1
Constraints:
3 <= arr.length <= 10^5
0 <= arr[i] <= 10^6
arr is guaranteed to be a mountain array.
Solution
Use binary search to solve this problem. For any middle index, it either locates at the left of the peak, or the right of the peak. If at the left, then discard the left half, otherwise discard the right half.文章来源：https://www.toymoban.com/news/detail-607272.html
Time complexity:
o
(
log
n
)
o(\log n)
o(logn)
Space complexity:
o
(
1
)
o(1)
o(1)文章来源地址https://www.toymoban.com/news/detail-607272.html
Code
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) >> 1
if arr[mid - 1] < arr[mid] and arr[mid + 1] < arr[mid]:
return mid
elif arr[mid - 1] < arr[mid]:
left = mid + 1
elif arr[mid + 1] < arr[mid]:
right = mid
到了这里，关于leetcode - 852. Peak Index in a Mountain Array的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
