專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

一網友說為什么華子在親戚長輩面前風評那么好，一聽說簽了華為都認為是年薪百萬。在華為年薪百萬也不是不可能，但至少要18級以上。大約7、8年能升到16級，再往上升就較難。18級以下占比最多，18級是個坎，往上升需要重新考評，答辯。如果沒有特殊招聘，一般需要十年以上的時間才能達到18級，也就相當于35歲之后了。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第162題：尋找峰值。

問題描述

來源：LeetCode第162題

難度：中等

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

• -2^31 <= nums[i] <= 2^31 - 1

• 對于所有有效的 i 都有 nums[i] != nums[i + 1]

問題分析

這題讓找出數組中的峰值，因為nums[-1] = nums[n] = -∞ ，也就是默認數組兩邊的值（實際上是不存在的）是負無窮大，所以數組中肯定是有峰值的。如果沒有時間復雜度的限制，這題就是一道非常簡單的題，直接遍歷數組中的每個值然后與兩邊比較即可。

但這題要求的時間復雜度是O(log n) ，所以我們只能使用二分查找，每次用中間的值nums[mid]和它的下一個值nums[mid+1]比較哪個大，因為提示中說了 對于所有有效的 i 都有 nums[i] != nums[i + 1] ，所以大的那邊一定有峰值。

JAVA：

public int findPeakElement(int[] nums) {     int left = 0;     int right = nums.length - 1;     while (left < right) {         int mid1 = (left + right) >>> 1;         int mid2 = mid1 + 1;         if (nums[mid1] < nums[mid2])             left = mid2;// 右邊肯定有峰值         else             right = mid1;// 左邊肯定有峰值     }     return left; }

C++：

public:     int findPeakElement(vector

 & nums) {         int left = 0;         int right = nums.size() - 1;         while (left < right) {             int mid1 = left +(right-left)/2;             int mid2 = mid1 + 1;             if (nums[mid1] < nums[mid2])                 left = mid2;// 右邊肯定有峰值             else                 right = mid1;// 左邊肯定有峰值         }         return left;     }

Python：

def findPeakElement(self, nums: List[int]) -> int:     left, right = 0, len(nums) - 1     while left < right:         mid1 = left + ((right - left) >> 1)         mid2 = mid1 + 1         if nums[mid1] < nums[mid2]:             left = mid2  # 右邊肯定有峰值         else:             right = mid1  # 左邊肯定有峰值     return left

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。