你給出一個整數數組(size為n)，其具有以下特點：

• 相鄰位置的數字是不同的
• A[0] < A[1] 并且 A[n - 2] > A[n - 1]

假定P是峰值的位置則滿足A[P] > A[P-1]且A[P] > A[P+1]，返回數組中任意一個峰值的位置。

樣例

給出數組[1, 2, 1, 3, 4, 5, 7, 6]返回1, 即數值 2 所在位置, 或者6, 即數值 7 所在位置.

題意實際應該是找任意一個極大值

class Solution:"""@param: A: An integers array.@return: return any of peek positions."""def findPeak(self, A):# write your code hereif len(A)<2:return A
for i in range(1,len(A)-1):if (A[i+1]-A[i]) < 0:return i

時間復雜度O(n)，Time Limit Exceeded

考慮二分法，九章參考：

class Solution:#@param A: An integers list.#@return: return any of peek positions.def findPeak(self, A):# write your code herestart, end = 1, len(A) - 2while start + 1 < end:mid = (start + end) / 2if A[mid] < A[mid - 1]:end = midelif A[mid] < A[mid + 1]:start = midelse:end = mid #直接return mid就行，不用再找了if A[start] < A[end]:return endelse:return start

一開始覺得不對，仔細審題發現還有約束

• A[0] < A[1] 并且 A[n - 2] > A[n - 1]

?

只用考慮中間點局部范圍則可以找到某峰值的區間。

轉載于:https://www.cnblogs.com/zhangli-ncu/p/8032034.html

總結

以上是生活随笔為你收集整理的lintcode_75.寻找峰值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。