Leetcode 852 山脉数组的封顶值索引

Time: 2019-08-07
难度：简单

题目描述

我们把符合下列属性的数组 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]
给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

本题最差的做法就是O(n)时间复杂度的暴力搜索算法。
最优解是时间复杂度为O(logn)的二分法。

但是这题的二分思路不是非常明确，需要一点点思考。

代码

class Solution:
   def is_increasing(self, a, b):
       return a < b
   def peakIndexInMountainArray(self, nums: List[int]) -> int:
       if nums == None or len(nums) == 0:
           return -1
       # 一定需要的是二分法才比较合适
       start, end = 0, len(nums) - 1
       while start + 1 < end:
           mid = start + (end - start) // 2
           if self.is_increasing(nums[mid], nums[mid+1]):
               start = mid
           else:
               end = mid
       print("start, end: ", start, end)

       if nums[start] < nums[end]:
           return end
       return start

时空复杂度分析

时间复杂度：
空间复杂度：

类似的题目

Leetcode 162: 寻找峰值

END.