目錄

1. 尋找峰值

1.1 題目解析

1.2 解法

1.3 代碼實現

2. 山脈數組

2.1 題目解析

2.2 解法

2.3 代碼實現

---

1. 尋找峰值

162. 尋找峰值 - 力扣（LeetCode）

峰值元素是指其值嚴格大于左右相鄰值的元素。

給你一個整數數組?nums，找到峰值元素并返回其索引。數組可能包含多個峰值，在這種情況下，返回?任何一個峰值?所在位置即可。

你可以假設?nums[-1] = nums[n] = -∞?。

你必須實現時間復雜度為?O(log n)?的算法來解決此問題。

示例 1：

輸入：nums = [1,2,3,1]
輸出：2
解釋：3 是峰值元素，你的函數應該返回其索引 2。

示例?2：

輸入：nums = [1,2,1,3,5,6,4]輸出：1 或 5 
解釋：你的函數可以返回索引 1，其峰值元素為 2；或者返回索引 5， 其峰值元素為 6。

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 對于所有有效的?i?都有?nums[i] != nums[i + 1]

1.1 題目解析

• 目標：在“嚴格先升后降”的山脈數組中找到唯一峰頂下標 i，滿足
  arr[0] < … < arr[i-1] < arr[i] > arr[i+1] > … > arr[n-1]。

• 關鍵結構（可二分的二段性）：定義性質 P(k) := arr[k] > arr[k-1]（是否還在上坡）。 在區間 k ∈ [1, n-2] 上，P(k) 呈先真后假：峰頂及其左側為真，峰頂右側為假。 因此問題等價于：在 [1, n-2] 中找“最后一個使 P(k) 為真”的位置 → 即峰頂。

• 搜索區間：為避免越界并且不丟解，取 [1, n-2]（峰不在兩端，且要訪問 k-1）。

• 收斂策略：配合“上中位數”與單側保留（上坡保留 mid），保證每輪縮小區間，最終 left == right。

• 復雜度：時間 O(log n)，空間 O(1)。

1.2 解法

i）對 P(k) := arr[k] > arr[k-1] 做“最后一個真”的二分查找

ii）若 arr[mid] > arr[mid-1]（上坡/在峰左側或即將到峰），峰一定在 [mid, right]，令 left = mid（保留 mid）。

iii）否則（下坡），峰一定在 [left, mid-1]，令 right = mid - 1。

iiii）用上中位數避免死循環；終止時 left == right 即峰頂。

正確性要點：

• 不變量：每輪后峰頂始終在 [left, right]。

• 收斂性：上中位數 + 上坡時 left = mid 保證區間嚴格縮小。

• 復雜度：O(log n) / O(1)。

1.3 代碼實現

class Solution {public int peakIndexInMountainArray(int[] arr) {int left = 1, right = arr.length - 2; // 峰不在兩端，且要用到 mid-1while (left < right) {int mid = left + (right - left + 1) / 2; // 上中位數if (arr[mid] > arr[mid - 1]) {left = mid;          // 上坡：峰在 [mid, right]} else {right = mid - 1;     // 下坡：峰在 [left, mid-1]}}return left; // 即峰頂索引}
}

2. 山脈數組

852. 山脈數組的峰頂索引 - 力扣（LeetCode）

給定一個長度為?n?的整數?山脈?數組?arr?，其中的值遞增到一個?峰值元素?然后遞減。

返回峰值元素的下標。

你必須設計并實現時間復雜度為?O(log(n))?的解決方案。

示例 1：

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

示例 2：

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

示例 3：

輸入：arr = [0,10,5,2]
輸出：1

提示：

• 3 <= arr.length <= 105
• 0 <= arr[i] <= 106
• 題目數據?保證?arr?是一個山脈數組

2.1 題目解析

• 目標：在“嚴格先升后降”的數組（山脈數組）里找到峰頂下標 i，滿足 arr[0] < ... < arr[i-1] < arr[i] > arr[i+1] > ... > arr[n-1]。 峰值不在兩端，且一定唯一。

• 本質：這是在上升段與下降段的分界點上找位置。 設性質 P(k) := arr[k] > arr[k-1]（“還在上坡”）。 在山脈數組中：：

  • 峰頂及其左側：P(k) 恒為 真（還在上坡或剛到頂的左側觀察點）。

  • 峰頂右側：P(k) 恒為 假（已經下坡）。因而在區間 k ∈ [1, n-1]，P(k) 呈現先真后假的“二段性”。我們要找的就是“最后一個使 P(k) 為真”的 k，它正是峰頂索引。

• 為何能用二分：有了“先真后假”的結構，就能用二分在 P(k) 上做“找最后一個真”。這比線性掃描把復雜度從 O(n) 降到 O(log n)。

• 邊界與越界：為了比較 arr[mid] 與 arr[mid-1]，mid 最小得是 1； 又因為峰不在兩端，最大可到 n-2。 所以把搜索區間定為 [1, n-2]，既不丟解也不越界。

• 三種位置類型與判斷：
  從“趨勢”角度看，mid 可能在：

  1. 上升段：arr[mid] > arr[mid-1]（繼續上坡）

  2. 下降段：arr[mid] < arr[mid-1]（已下坡）

  3. 峰頂：滿足 arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1] 實際實現里只用“與左鄰比較”也足夠：峰頂在“與左鄰比較為真”的那一段的最右端，所以按“找最后一個真”就能把指針收斂到峰頂；無需顯式判斷右鄰。

2.2 解法

i）在閉區間 left = 1, right = n-2 上二分（峰不在兩端，且我們要用到 arr[mid-1]）。

ii）取上中位數：mid = left + (right - left + 1) / 2。

iii）若 arr[mid] > arr[mid - 1]（仍在上坡），則峰一定在 [mid, right]，令 left = mid。

iiii）否則（已在下坡），峰一定在 [left, mid - 1]，令 right = mid - 1。

iiiii）直到 left == right，即為峰頂索引，返回之。

正確性要點

• 不變量：峰頂始終在 [left, right]。

  • 上坡保留 [mid, right] 不丟峰；

  • 下坡保留 [left, mid-1] 不丟峰。

• 收斂性：選“上中位數”并在上坡時賦 left = mid，保證區間嚴格縮小，終將 left == right。

• 復雜度：時間 O(log n)，空間 O(1)。

2.3 代碼實現

class Solution {public int peakIndexInMountainArray(int[] arr) {int n = arr.length;int left = 1, right = n - 2; // 峰不在兩端，且需訪問 arr[mid-1]while (left < right) {int mid = left + (right - left + 1) / 2; // 上中位數if (arr[mid] > arr[mid - 1]) {// 上坡：峰在 [mid, right]，保留 midleft = mid;} else {// 下坡：峰在 [left, mid-1]，丟棄 midright = mid - 1;}}return left; // 或 right}
}