程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

【Leetcode刷題Python】852. 山脈數組的峰頂索引

編輯:Python

1 題目

符合下列屬性的數組 arr 稱為 山脈數組 :
arr.length >= 3
存在 i(0 < i < arr.length - 1)使得:
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
給你由整數組成的山脈數組 arr ,返回任何滿足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下標 i 。

示例 1:

輸入:arr = [0,1,0]
輸出:1

示例 2:

輸入:arr = [0,2,1,0]
輸出:1

2 解析

用二分查找的話,時間復雜度是Log(n)。思路是

  • 中間值大於後一個值的話,意思是已經爬坡過了峰值,那峰值一定在左邊部分
  • 中間值小於後一個值的話,還在爬坡,峰值在右部分

3 Python實現

class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
left,right = 0,len(arr)-1
result = 0
while left<=right:
mid = (left+right)//2
if arr[mid]>arr[mid+1]:
result = mid
right = mid-1
else:
left = mid+1
return result

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved