繼第 3 天的「121. Best Time to Buy and Sell Stock」，今天來解 162 這題！還沒看過第 3 天或再之前天數的朋友，歡迎也去看看~

我們開始吧！

前言

這題有在 MIT 6.006 演算法概論被提出來，有興趣了解詳細的朋友歡迎到文末參考相關影片和講義 :)

基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/find-peak-element

演算法與資料結構

• Divide and Conquer
• Array
• Binary Search

題意

給予一個 0-indexed 整數 nums 陣列，請回傳最高值元素 (peak element) ，如果有多個最高值，請回傳任一個最高值的索引。

最高值元素： 大於其臨近元素。

條件

You must write an algorithm that runs in O(log n) time.

題目中要求以 O(log n) 的時間複雜度完成。

不過作為比較，這篇會先以線性走訪解題，再來達成這個需求。

範例

nums = [1, 2, 3, 1]

peak 元素為 3 ，因此需回傳他的索引值：

2

1. 直覺解 - 一次走訪

規劃

核心邏輯

• 當前的值大於下一個元素，就可以視為 peak 並回傳當前索引

走訪

• 由於都要和下一個元素檢驗，因此只需走訪到陣列長度 - 1
• 當走訪完都無法找到 peak 的話，代表 peak 在最後一個，就可以回傳陣列長度 - 1 做為答案

程式碼

class Solution {
    func findPeakElement(_ nums: [Int]) -> Int {
        for index in 0..<(nums.count - 1) {
            if nums[index] > nums[index + 1] {
                return index
            }
        }
        return nums.count - 1
    }
}

執行結果

• Runtime: 21 ms (Beats 59.36%)
• Memory: 14.16 MB (Beats 16.33%)

複雜度分析

2. 二元搜尋

題目提到需要以 O(log n) 的時間複雜度解題，因此就可以用二元搜尋來解題。因為二元搜尋是能夠將 O(n) 降為 O(log n) 的主要工具之一。

因此

只要看到題目提到 O(log n) 就要想到可能可以用二元搜尋來解題

規劃

簡要介紹二元搜尋

二元搜尋是透過中間點比較中間點、左半邊和右半邊的演算法，優點就是經過一次的比較舊能夠去掉一半不需要比較，從而大大改善運行時間。

核心 routine

因此這題只要以二元搜尋的演算法為原型來變化即可，因此我們要定下三個主要的邏輯

1. 定義應該要選 左半邊 的條件
2. 定義應該要選 右半邊 的條件

條件和處理方式如下

程式碼

class Solution {
    func findPeakElement(_ nums: [Int]) -> Int {
        var left = 0
        var right = nums.count - 1

        while left < right {
            let middle = (left + right) / 2
            if nums[middle] > nums[middle + 1] {
                right = middle
            } else {
                left = middle + 1
            }
        }
        return left
    }
}

執行結果

• Runtime: 14 ms (Beats 99.60%)
• Memory: 13.66 MB (Beats 99.20%)

複雜度分析

解法比較

可能是測試案例的關係，線性走訪和二元搜尋兩者的 runtime 會很接近，有時候甚至線性走訪會比較快。不過就時間複雜度來說，二元搜尋還是佔優勢。

參照

• MIT 6.006 Introduction to Algorithms, Fall 2011 公開課程 (27:40~) - YouTube
  • 課程講義 Peak finding - PDF

結語

如果有任何回饋或是文中寫不清楚的地方，歡迎在下面留言！

今天就到這裡，明天見！