題目
#

leetcode 852 - Peak Index in a Mountain Array(題目說明請點連結)

題目簡述
#

給定一個山形陣列，找出峰值元素的索引。

Example 1:

Input: arr = [0,1,0]
Output: 1
Explanation: 峰值在索引 1 的位置。

Example 2:

Input: arr = [0,2,1,0]
Output: 1
Explanation: 峰值在索引 1 的位置。

Example 3:

Input: arr = [0,10,5,2]
Output: 1
Explanation: 峰值在索引 1 的位置。

解題思路
#

問題理解
#

給定一個山形陣列（mountain array），找出峰值元素的索引。
山形陣列的特點：

陣列長度 >= 3
存在一個峰值，峰值左側嚴格遞增，右側嚴格遞減
峰值是陣列中的最大值

二分搜索策略
#

使用二分搜索來尋找峰值，因為山形陣列具有單調性：

在峰值左側：arr[i] < arr[i+1]（遞增）
在峰值右側：arr[i] > arr[i+1]（遞減）
在峰值位置：arr[i-1] < arr[i] > arr[i+1]

算法步驟
#

初始化左右指針：left = 0, right = arr.length - 1
在 left < right 的條件下進行二分搜索
計算中間位置：mid = left + (right - left) / 2
比較 arr[mid] 與 arr[mid+1]：
- 如果 arr[mid] < arr[mid+1]：峰值在右側，移動左指針
- 如果 arr[mid] >= arr[mid+1]：峰值在左側或當前位置，移動右指針
當 left == right 時，找到峰值位置

例子說明
#

arr = [0,2,1,0]

初始狀態：left = 0, right = 3
第一次二分：mid = 1
- arr[1] = 2, arr[2] = 1
- arr[1] > arr[2]，所以峰值在左側或當前位置
- right = mid = 1
第二次二分：left = 0, right = 1, mid = 0
- arr[0] = 0, arr[1] = 2
- arr[0] < arr[1]，所以峰值在右側
- left = mid + 1 = 1
結束條件：left = 1, right = 1
返回結果：left = 1

完整程式碼
#

java

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0; // 初始化左指針
        int right = arr.length - 1; // 初始化右指針
        int mid; // 中間位置

        while (left < right) { // 當左右指針未相遇時繼續搜索
            mid = left + (right - left) / 2; // 計算中間位置
            if (arr[mid] < arr[mid + 1]) { // 如果中間位置小於右側
                left = mid + 1; // 峰值在右側，移動左指針
            } else { // 如果中間位置大於等於右側
                right = mid; // 峰值在左側或當前位置，移動右指針
            }
        }
        
        return left; // 返回峰值位置
    }
}