852. Peak Index in a Mountain Array 山脉数组的峰顶索引

@TOC

# 题目描述

Let's call an array A a mountain if the following properties hold:

1. `A.length >= 3`
2. There exists some `0 < i < A.length - 1` such that `A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]`

Given an array that is definitely a mountain, return any i such that `A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]`.

Example 1:

``````Input: [0,1,0]
Output: 1
``````

Example 2:

``````Input: [0,2,1,0]
Output: 1
``````

Note:

1. 3 <= A.length <= 10000
2. 0 <= A[i] <= 10^6
3. A is a mountain, as defined above.

# 解题方法

# 二分查找

``````class Solution(object):
def peakIndexInMountainArray(self, A):
"""
:type A: List[int]
:rtype: int
"""
left, right = 0, len(A) - 1
while left < right:
mid = (left + right) / 2
if A[mid - 1] < A[mid] and A[mid] < A[mid + 1]:
left = mid
elif A[mid - 1] > A[mid] and A[mid] > A[mid + 1]:
right = mid
else:
break
return mid
``````

``````class Solution:
def peakIndexInMountainArray(self, A):
"""
:type A: List[int]
:rtype: int
"""
N = len(A)
left, right = 0, N
while left < right:
mid = left + (right - left) // 2
if A[mid - 1] < A[mid] and A[mid] > A[mid + 1]:
return mid
if A[mid] < A[mid + 1]:
left = mid + 1
else:
right = mid
return -1
``````

# 查找最大值位置

``````class Solution:
def peakIndexInMountainArray(self, A):
"""
:type A: List[int]
:rtype: int
"""
return A.index(max(A))
``````

# 寻找第一个下降的位置

``````class Solution:
def peakIndexInMountainArray(self, A):
"""
:type A: List[int]
:rtype: int
"""
for i in range(len(A) - 1):
if A[i + 1] < A[i]:
return i
return -1
``````

# 日期

2018 年 6 月 17 日 —— 端午节也在刷题2333 2018 年 11 月 5 日 —— 打了羽毛球，有点累