題目描述：峰值元素是指其值大于左右相鄰值的元素。給你一個輸入數(shù)組 nums，找到峰值元素并返回其索引。數(shù)組可能包含多個峰值，在這種情況下，返回 任何一個峰值 所在位置即可。你可以假設 nums[-1] = nums[n] = -∞ 。
示例：
例1
輸入：nums = [1,2,3,1]
輸出：2
解釋：3 是峰值元素，你的函數(shù)應該返回其索引 2。
例2
輸入：nums = [1,2,1,3,5,6,4]
輸出：1 或 5
解釋：你的函數(shù)可以返回索引 1，其峰值元素為 2；
或者返回索引 5， 其峰值元素為 6。
提示：
- 1 <= nums.length <= 1000
- -231 <= nums[i] <= 231 - 1
- 對于所有有效的 i 都有 nums[i] != nums[i + 1]
題解一：線性掃描
解題思路：從數(shù)組下標為i = 0的位置開始比較 nums[i] > nums[i+1]是否成立，如果成立，則i即為我們要找的下標，如果找到最后都不滿足nums[i] > nums[i+1]，則說明該數(shù)組是一個升序數(shù)組，最后一個元素即為峰值
解惑：為什么沿著i = 0的位置開始比較 nums[i] > nums[i+1]，成立后i即為所找下標，因為沿著數(shù)組能找到i的位置，說明i之前的元素都不滿足nums[i] > nums[i+1]， 即 i位置之前的元素都小于i位置的元素值，即滿足峰值大于左右兩側中的左側。
解題語言： Swift
static func findPeakElement(nums: [Int]) -> Int {
for i in 0..<nums.count - 1 {
if nums[i] > nums[i+1] {
return i
}
}
return nums.count - 1
}
復雜度分析：
時間復雜度：O(n)，我們對長度為 n 的數(shù)組 nums 只進行一次遍歷。
空間復雜度: O(1), 只使用了常數(shù)空間。
題解二：二分查找
解題思路： 我們可以將 nums 數(shù)組中的任何給定序列視為交替的升序和降序序列。通過利用這一點，以及“可以返回任何一個峰作為結果”的要求，我們可以利用二分查找來找到所需的峰值元素。通過每一步減少搜索空間來找到所需數(shù)字，首先從數(shù)組 nums 中找到中間的元素mid。若該元素恰好位于降序序列或者一個局部下降坡度中（通過將 nums[i] 與右側比較判斷)，則說明峰值會在本元素的左邊。于是，我們將搜索空間縮小為 mid 的左邊(包括其本身)，并在左側子數(shù)組上重復上述過程。若該元素恰好位于升序序列或者一個局部上升坡度中（通過將 nums[i] 與右側比較判斷)，則說明峰值會在本元素的右邊。于是，我們將搜索空間縮小為 mid 的右邊，并在右側子數(shù)組上重復上述過程。就這樣，我們不斷地縮小搜索空間，直到搜索空間中只有一個元素，該元素即為峰值元素。
static func findPeakElementTre(nums: [Int]) -> Int {
var start = 0, end = nums.count - 1
while start < end {
let mid = (start + end) / 2
if nums[mid] > nums[mid + 1] {
end = mid
} else {
start = mid + 1
}
}
return start
}
復雜度分析：
時間復雜度：O(log2(n))，每一步都將搜索空間減半。因此，總的搜索空間只需要 log2 (n) 步。其中 n 為 nums 數(shù)組的長度。
空間復雜度: O(1), 只使用了常數(shù)空間。
