Time: 2019-08-07
難度：中等
題目描述
峰值元素是指其值大于左右相鄰值的元素。
給定一個輸入數(shù)組 nums，其中 nums[i] ≠ nums[i+1]佳鳖，找到峰值元素并返回其索引。
數(shù)組可能包含多個峰值，在這種情況下恋昼，返回任何一個峰值所在位置即可。
你可以假設(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) 時間復(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ù)該丟掉哪一半。
每次判斷完畢丟掉一半的算法但两，就是二分法鬓梅，時間復(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
這個代碼吧谨湘，執(zhí)行效率還沒下面這個高：
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
return nums.index(max(nums))
時空復(fù)雜度分析
時間復(fù)雜度：
空間復(fù)雜度：
相似題目
- 有效的山脈數(shù)組
- 山脈數(shù)組中的峰值
END.
