LeetCode 筆記 - 852. Peak Index in a Mountain Array

Posted on

題目在此 852. Peak Index in a Mountain Array

給定一個山形陣列 arr，請找出陣列中峰值（peak）的索引。山形陣列是指先遞增後遞減的陣列，且至少包含三個元素。

解題思維

這題可以使用二分搜尋法來解決，因為山形陣列的特性使得我們可以有效地縮小搜尋範圍。

我們可以從陣列的中間元素開始比較，並根據中間元素與其右側元素的大小關係來決定下一步的搜尋方向：

  • 如果中間元素小於其右側元素，表示峰值在右側，因此我們將搜尋範圍縮小到右半部。
  • 如果中間元素大於或等於其右側元素，表示峰值在左側或就是中間元素，因此我們將搜尋範圍縮小到左半部。

這樣持續進行，直到搜尋範圍縮小到只剩下一個元素，該元素即為峰值的索引。

Time complexity 是 $O(log n)$
因為每次搜尋都將範圍縮小一半。

Space complexity 是 $O(1)$
因為我們只使用了常數級別的額外空間來存儲索引。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:

        # step 0: binary search
        # step 1: mid is compare with the next element
        #         if arr[mid] < arr[mid + 1]: means mid index is at left side
        #         otherwise: mid index is at right side
        # step 2: return left index, arr[left] >= arr[left + 1]

        # time complexity: O(log n)
        # space complexity: O(1)

        left = 0
        right = len(arr) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            else:
                right = mid - 1

        return left

也許你也會想看看