符合下列屬性的陣列 arr 稱為 山峰陣列（山脈陣列） ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
給定由整陣列成的山峰陣列 arr ，回傳任何滿足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下標 i ，即山峰頂部，
示例 1： 輸入：arr = [0,1,0] 輸出：1 // 回傳下標
示例 2： 輸入：arr = [1,3,5,4,2] 輸出：2
示例 3： 輸入：arr = [0,10,5,2] 輸出：1
示例 4：輸入：arr = [3,4,5,1] 輸出：2
示例 5： 輸入：arr = [24,69,100,99,79,78,67,36,26,19] 輸出：2
思路：
主要是用到二分查找法去解決–具體文章看 👉 漫畫-二分查找
說到二叉樹，我也是轉載了別人的文章去解釋這個：
其實就是每次去取中間是跟需要找到數去比對那個更大，然后下一次的回傳就會縮小，例如：
給定范圍0到1000的整數：
第一次我們選擇500，發現偏大了，
那么下一次的選擇范圍，就變成了1到499：
第二次我們選擇250，發現還是偏大了，
那么下一次的選擇范圍，就變成了1到249：
第三次我們選擇125，發現偏小了，
那么下一次的選擇范圍，就變成了126到249：
以此類推，最壞的情況需要猜測多少次呢？
答案是 log1000 = 10次，
也就是讓原本的區間范圍進行10次 “折半”，
剛才我們所分析的是猜數字的游戲，
如果我們把場景轉換成最初的面試問題：
在包含1000個整型元素的有序陣列中查找某個特定整數，
又該如何去做呢？
同樣道理，
我們可以首先判斷下標是499的元素（因為陣列下標從0開始，到999結束），
如果元素大于要查找的整數，
我們再去判斷下標是249的元素，
然后判斷下標124的元素…
以此類推，直到最終找到想要的元素，
或者選擇范圍等于0為止，
上述這個程序，
就是所謂的二分查找演算法，
##下面是三種解法
1、二分查找法：
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function (arr: string | any[]): number {
let [low, high] = [0, arr.length - 1];
while (low <= high) {
const mid = (low + high) >> 1;
const midItem = arr[mid];
if (arr[mid - 1] > midItem) {
// 山脈的 前半部分
high = mid - 1;
} else if (arr[mid + 1] > midItem) {
// 山脈的 后半部分
low = mid + 1;
// 只有同時滿足倆個條件 那個數才是最大的
// 他需要大于左邊的數值 和 右邊的數值
} else if (midItem > arr[mid - 1] && midItem > arr[mid + 1]) {
return mid;
}
}
};
2、這是 遍歷每個數 去比對 找出最大的那個數 回傳下標
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function (arr: string | any[]): number {
let max = arr[0];
for(let i =1;i<arr.length;i++){
if(max > arr[i]){
return i-1;
}else{
max = arr[i];
}
}
};
3、js自帶的api已經就可以解決這個問題，我不知道這么用算不算違反題意😄
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function (arr: string | any[]): number {
return arr.indexOf(Math.max.apply(null,arr))
};
如果有幫助到你 麻煩給一個三連+關注,能看到博主的最新blog
感謝感謝
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/326033.html
標籤：其他
上一篇：unity3d 實作圓形小地圖
下一篇：卡片游戲 基礎c語言試題