一魚多吃 用 二分搜尋的觀念,來尋找絕對最大值 Peak Index in Mountain_Leetcode #852

更新於 發佈於 閱讀時間約 3 分鐘

這題題目在這裡:

Peak Index in a Mountain Array - LeetCode

題目會給定一個陣列,陣列裡面的元素分布就像一座山峰。

最大值的左邊都是上坡段,最大值的右邊都是下坡段。

要求我們找出陣列裡面的絕對極大值(absolute max value)所在的陣列索引

也就是說當下這個元素大於左邊鄰居的元素值,也大於右邊鄰居的元素值。

nums[i] > nums[i-1] > ... > nums[0] 且

nums[i] > nums[i+1] > ... > nums[n-1]

答案只會有一組解。


測試範例:

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

Example 3:

Input: arr = [0,10,5,2]
Output: 1

 


約束條件:

Constraints:

  • 3 <= arr.length <= 105
  • 0 <= arr[i] <= 106
  • arr is guaranteed to be a mountain array.

演算法:

先回顧一個基本性質,在已經排序好的陣列元素裡面搜尋,適合使用二分搜尋法

基本上和前一題用到的都是同樣的觀念,和鄰居去比較,
每次判斷是上坡還是下坡,去決定搜尋的方向。

假如現在是上坡絕對最大值肯定在我的右邊

假如現在是下坡絕對最大值肯定在我的左邊

raw-image

程式碼:

class Solution:
 def peakIndexInMountainArray(self, arr: List[int]) -> int:
  
  
  def helper(nums, left, right):
  
   if left == right:
    # base case:
    return left
   
   mid = ( left + right ) // 2
   
   # general case
   if nums[mid] > nums[mid+1]:
    # peak is either nums[mid] or on the left hand side
    return helper(nums, left, mid)
   else:
    # peak is either nums[mid+1] or on the right hand side
    return helper(nums, mid+1, right)
   

   
  return helper( arr, 0 , len(arr)-1)



時間複雜度:

O( log n ) : 每次都能淘汰一半不可能的區間,最多花費O( log n )次可以找到絕對最大值,也就是山峰。

空間複雜度:

O( log n ): 遞迴stack深度最大為O( log n ),最多花費O( log n )層可以抵達終止條件。


這題學完,記得去複習經典的Binary searchSearch a 2D MatrixSqrt(x)
Find Peak Element,背後的二分搜尋法原理和對半切從中心點去逼近解答、目標值的想法都是相通的喔!


Reference:

[1] Peak Index in a Mountain Array - LeetCode

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/08/14
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
2024/08/14
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
2024/05/27
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
Thumbnail
2024/05/27
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
Thumbnail
2024/03/19
這篇文章,會帶著大家複習以前學過的二分搜尋法(Binary Search)框架, 並且以二分搜尋法的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個實用的演算法框架。 Binary search 二分搜尋法框架 用途: 在已經排序好的數列中尋找目標值。
Thumbnail
2024/03/19
這篇文章,會帶著大家複習以前學過的二分搜尋法(Binary Search)框架, 並且以二分搜尋法的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個實用的演算法框架。 Binary search 二分搜尋法框架 用途: 在已經排序好的數列中尋找目標值。
Thumbnail
看更多
你可能也想看
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
題目敘述 題目會給定一個陣列nums 和 給定的k值,要求我們找出陣列裡第k大的元素。 題目的原文敘述 測試範例 Example 1: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 第二大的元素為5​ Example 2: Input:
Thumbnail
題目敘述 題目會給定一個陣列nums 和 給定的k值,要求我們找出陣列裡第k大的元素。 題目的原文敘述 測試範例 Example 1: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 第二大的元素為5​ Example 2: Input:
Thumbnail
題目敘述 題目會給定一個整數陣列nums,要求我們找出最大的兩個整數a, b,返回(a-1) * (b-1)的乘積。 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [3,4,5,2] Output: 12
Thumbnail
題目敘述 題目會給定一個整數陣列nums,要求我們找出最大的兩個整數a, b,返回(a-1) * (b-1)的乘積。 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [3,4,5,2] Output: 12
Thumbnail
題目會給們一個陣列,還有一個k值。 好陣列定義是: 有包含nums[k]的子陣列。 分數定義是: min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 其中, i, j 分別是子陣列的左端點和右端點 請問,好的子陣列的最大分數是多少?
Thumbnail
題目會給們一個陣列,還有一個k值。 好陣列定義是: 有包含nums[k]的子陣列。 分數定義是: min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 其中, i, j 分別是子陣列的左端點和右端點 請問,好的子陣列的最大分數是多少?
Thumbnail
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
Thumbnail
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
Thumbnail
題目會給我們一個山形的輸入陣列,和目標值target,要求我們找出目標值所在的陣列索引。如果出現兩次,返回比較小的那一個,也就是比較靠左的那個索引值。 山形的意思就是說,從最左側到山頂最大值都是遞增,從山頂最大值到右側都是遞減。
Thumbnail
題目會給我們一個山形的輸入陣列,和目標值target,要求我們找出目標值所在的陣列索引。如果出現兩次,返回比較小的那一個,也就是比較靠左的那個索引值。 山形的意思就是說,從最左側到山頂最大值都是遞增,從山頂最大值到右側都是遞減。
Thumbnail
題目給定一個已排序的輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
Thumbnail
題目給定一個已排序的輸入陣列,陣列裡面的數字自分別代表每篇論文的被引用數。 要求我們計算h-index。 h-index的定義: 找一個最大的h值,使得有h篇論文,個別論文的被引用數都 大於等於 h
Thumbnail
題目會給一個輸入陣列,裡面的數字分別代表每個index對應到的高度,要求我們計算山峰與低谷的數目,總共有多少個。 山峰 Hill: 比最靠近高度不相同的兩個鄰居的高度還要高。 低谷 Valley:比最靠近高度不相同的兩個鄰居的高度還要低。
Thumbnail
題目會給一個輸入陣列,裡面的數字分別代表每個index對應到的高度,要求我們計算山峰與低谷的數目,總共有多少個。 山峰 Hill: 比最靠近高度不相同的兩個鄰居的高度還要高。 低谷 Valley:比最靠近高度不相同的兩個鄰居的高度還要低。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News