Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
Example 1:
Input: nums = [1, 2, 4, 8, 6, 3]
Output: 8
Example 2:
Input: nums = [10, 9, 8, 7],
Output: 10
class Solution:
"""
@param nums: a mountain sequence which increase firstly and then decrease
@return: then mountain top
"""
def mountainSequence(self, nums):
# less than 2 elements
if len(nums) == 0:
# no such case
return "nimei"
if len(nums) <= 2:
return max(nums)
# corner cases: not increase or decrease at all
if nums[0] > nums[1]:
return nums[0]
if nums[-1] > nums[-2]:
return nums[-1]
# init
low = 0
up = len(nums) - 1
# binary search loop
while low < up - 1:
mid = (low + up) // 2
if nums[mid] < nums[mid + 1]:
low = mid
if nums[mid] > nums[mid + 1]:
up = mid
if nums[mid] == nums[mid + 1]:
# no such case
return "nimei"
# definitly up
return nums[up]
question
special care