Time: 2019-08-07
難度：中等

題目描述

峰值元素是指其值大于左右相鄰值的元素。

給定一個(gè)輸入數(shù)組 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

數(shù)組可能包含多個(gè)峰值，在這種情況下，返回任何一個(gè)峰值所在位置即可。

你可以假設(shè) nums[-1] = nums[n] = -∞。

示例 1:

輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素，你的函數(shù)應(yīng)該返回其索引 2。
示例 2:

輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5
解釋: 你的函數(shù)可以返回索引 1，其峰值元素為 2；
或者返回索引 5， 其峰值元素為 6。
說明:

你的解法應(yīng)該是 O(logN) 時(shí)間復(fù)雜度的。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-peak-element
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

思路

也是一樣的，用二分法來做，判斷mid數(shù)字處在的位置是否為上升或下降區(qū)間，以此為依據(jù)該丟掉哪一半。

每次判斷完畢丟掉一半的算法，就是二分法，時(shí)間復(fù)雜度就是。

代碼

class Solution:
    def findPeakElement(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
        else:
            return start
        
    def is_increasing(self, a, b):
        return a < b

這個(gè)代碼吧，執(zhí)行效率還沒下面這個(gè)高：

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        return nums.index(max(nums))

時(shí)空復(fù)雜度分析

時(shí)間復(fù)雜度：
空間復(fù)雜度：

相似題目

941. 有效的山脈數(shù)組
942. 山脈數(shù)組中的峰值

END.