優質博文IT-BLOG-CN

一、題目

峰值元素是指其值嚴格大于左右相鄰值的元素。給你一個整數數組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]

二、代碼

方案一：尋找最大值

由于題目保證了nums[i]≠nums[i+1]，那么數組nums中最大值兩側的元素一定嚴格小于最大值本身。因此，最大值所在的位置就是一個可行的峰值位置。

我們對數組nums進行一次遍歷，找到最大值對應的位置即可。

class Solution {public int findPeakElement(int[] nums) {int idx = 0;for (int i = 1; i < nums.length; ++i) {if (nums[i] > nums[idx]) {idx = i;}}return idx;}
}

時間復雜度： O(n)，其中n是數組nums的長度。
空間復雜度： O(1)。

方案二：二分查找

首先要注意題目條件，在題目描述中出現了nums[-1] = nums[n] = -∞，這就代表著 只要數組中存在一個元素比相鄰元素大，那么沿著它一定可以找到一個峰值。

根據上述結論，我們就可以使用二分查找找到峰值

查找時，左指針l，右指針r，以其保持左右順序為循環條件

根據左右指針計算中間位置m，并比較m與m+1的值，如果m較大，則左側存在峰值，r = m，如果m + 1較大，則右側存在峰值，l = m + 1

class Solution {public int findPeakElement(int[] nums) {int left = 0, right = nums.length - 1;for (; left < right; ) {int mid = left + (right - left) / 2;if (nums[mid] > nums[mid + 1]) {right = mid;} else {left = mid + 1;}}return left;}
}

時間復雜度： O(log?n)，其中n是數組nums的長度。
空間復雜度： O(1)。

方案三：迭代爬坡

俗話說「人往高處走，水往低處流」。如果我們從一個位置開始，不斷地向高處走，那么最終一定可以到達一個峰值位置。

因此，我們首先在[0,n)的范圍內隨機一個初始位置i，隨后根據nums[i?1],nums[i],nums[i+1]三者的關系決定向哪個方向走：
【1】如果nums[i?1]<nums[i]>nums[i+1]，那么位置i就是峰值位置，我們可以直接返回i作為答案；
【2】如果nums[i?1]<nums[i]<nums[i+1]，那么位置i處于上坡，我們需要往右走，即i←i+1；

如果nums[i?1]>nums[i]>nums[i+1]，那么位置i處于下坡，我們需要往左走，即i←i?1；

如果nums[i?1]>nums[i]<nums[i+1]，那么位置i位于山谷，兩側都是上坡，我們可以朝任意方向走。

如果我們規定對于最后一種情況往右走，那么當位置i不是峰值位置時：
【1】如果nums[i]<nums[i+1]，那么我們往右走；
【2】如果nums[i]>nums[i+1]，那么我們往左走。

class Solution {public int findPeakElement(int[] nums) {int n = nums.length;int idx = (int) (Math.random() * n);while (!(compare(nums, idx - 1, idx) < 0 && compare(nums, idx, idx + 1) > 0)) {if (compare(nums, idx, idx + 1) < 0) {idx += 1;} else {idx -= 1;}}return idx;}// 輔助函數，輸入下標 i，返回一個二元組 (0/1, nums[i])// 方便處理 nums[-1] 以及 nums[n] 的邊界情況public int[] get(int[] nums, int idx) {if (idx == -1 || idx == nums.length) {return new int[]{0, 0};}return new int[]{1, nums[idx]};}public int compare(int[] nums, int idx1, int idx2) {int[] num1 = get(nums, idx1);int[] num2 = get(nums, idx2);if (num1[0] != num2[0]) {return num1[0] > num2[0] ? 1 : -1;}if (num1[1] == num2[1]) {return 0;}return num1[1] > num2[1] ? 1 : -1;}
}

時間復雜度： O(n)，其中n是數組nums的長度。在最壞情況下，數組nums單調遞增，并且我們隨機到位置0，這樣就需要向右走到數組nums的最后一個位置。
空間復雜度： O(1)。

方法四：二分查找優化

我們可以發現，如果nums[i]<nums[i+1]，并且我們從位置i向右走到了位置i+1，那么位置i左側的所有位置是不可能在后續的迭代中走到的。

這是因為我們每次向左或向右移動一個位置，要想「折返」到位置i以及其左側的位置，我們首先需要在位置i+1向左走到位置i，但這是不可能的。

并且根據方法二，我們知道位置i+1以及其右側的位置中一定有一個峰值，因此我們可以設計出如下的一個算法：
【1】對于當前可行的下標范圍[l,r]，我們隨機一個下標i；
【2】如果下標i是峰值，我們返回i作為答案；
【3】如果nums[i]<nums[i+1]，那么我們拋棄[l,i]的范圍，在剩余[i+1,r]的范圍內繼續隨機選取下標；
【4】如果nums[i]>nums[i+1]，那么我們拋棄[i,r]的范圍，在剩余[l,i?1]的范圍內繼續隨機選取下標。

在上述算法中，如果我們固定選取i為[l,r]的中點，那么每次可行的下標范圍會減少一半，成為一個類似二分查找的方法，時間復雜度為 O(log?n)。

class Solution {public int findPeakElement(int[] nums) {int n = nums.length;int left = 0, right = n - 1, ans = -1;while (left <= right) {int mid = (left + right) / 2;if (compare(nums, mid - 1, mid) < 0 && compare(nums, mid, mid + 1) > 0) {ans = mid;break;}if (compare(nums, mid, mid + 1) < 0) {left = mid + 1;} else {right = mid - 1;}}return ans;}// 輔助函數，輸入下標 i，返回一個二元組 (0/1, nums[i])// 方便處理 nums[-1] 以及 nums[n] 的邊界情況public int[] get(int[] nums, int idx) {if (idx == -1 || idx == nums.length) {return new int[]{0, 0};}return new int[]{1, nums[idx]};}public int compare(int[] nums, int idx1, int idx2) {int[] num1 = get(nums, idx1);int[] num2 = get(nums, idx2);if (num1[0] != num2[0]) {return num1[0] > num2[0] ? 1 : -1;}if (num1[1] == num2[1]) {return 0;}return num1[1] > num2[1] ? 1 : -1;}
}

時間復雜度： O(log?n)，其中n是數組nums的長度。
空間復雜度： O(1)。