新计划编程入门

数组&字符串

山脉数组的顶峰索引

难度：普通

给定一个长度为 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

方法一

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

复杂度分析
时间复杂度：O(n)，其中 n 是数组 arr 的长度。我们最多需要对数组 arr 进行一次遍历。
空间复杂度：O(1)。

方法二

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