牛客網(wǎng)高頻算法題系列-BM19-尋找峰值
題目描述
給定一個長度為n的數(shù)組nums驯镊，請你找到峰值并返回其索引葫督。數(shù)組可能包含多個峰值，在這種情況下板惑，返回任何一個所在位置即可橄镜。
- 峰值元素是指其值嚴格大于左右相鄰值的元素。嚴格大于即不能有等于
- 假設(shè) nums[-1] = nums[n] = -\infty?∞
- 對于所有有效的 i 都有 nums[i] != nums[i + 1]
- 你可以使用O(logN)的時間復(fù)雜度實現(xiàn)此問題嗎冯乘？
原題目見：尋找峰值
解法一：數(shù)組遍歷
首先洽胶，判斷幾種特殊場景：
- 如果數(shù)組為空，則不存在峰值裆馒；
- 如果數(shù)組只有一個元素姊氓，因為都是負無窮，所以第一個元素即為峰值喷好；
- 如果數(shù)組的第一個元素比第二個元素大翔横，加上左邊負無窮，則第一個元素必為峰值梗搅；
- 如果數(shù)組的最后一個元素比倒數(shù)二個元素大禾唁，加上右邊邊負無窮舔亭，則倒數(shù)第一個元素必為峰值。
如果不存在以上特殊情況蟀俊，則從數(shù)組的第二位開始遍歷數(shù)組钦铺，判斷是否是峰值。
解法一：二分法
原理：因為左右都是負無窮肢预，對于中間的元素矛洞，如果nums[mid] > nums[mid + 1]，也就是mid部分遞減烫映，加上左邊負無窮沼本，所以mid的左邊一定會有峰值；同理锭沟，如果nums[mid] < nums[mid + 1]抽兆，加上右邊負無窮，所以mid的右邊一定會有峰值族淮。
代碼
public class Bm019 {
/**
* 遍歷數(shù)組
*
* @param nums
* @return
*/
public static int findPeakElement(int[] nums) {
// 如果數(shù)組為空辫红，則不存在峰值
if (nums == null) {
return -1;
}
// 如果數(shù)組的長度為1，則首位即為峰值
if (nums.length == 1) {
return 0;
}
// 如果第一位比第二位大祝辣，則第一位必為峰值
if (nums[0] > nums[1]) {
return 0;
}
// 如果最后一位比倒數(shù)第二位大贴妻，則最后一位必為峰值
if (nums[nums.length - 1] > nums[nums.length - 2]) {
return nums.length - 1;
}
// 如果前面的幾種特殊場景不存在，則遍歷數(shù)組中的元素蝙斜，逐一判斷是否是峰值
for (int i = 1; i < nums.length - 1; i++) {
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
return i;
}
}
return -1;
}
/**
* 二分法
* 原理：因為左右都是負無窮名惩，對于中間的元素，如果nums[mid] > nums[mid + 1]孕荠，就是mid部分遞減娩鹉，加上左邊負無窮，
* 所以mid的左邊一定會有峰值稚伍；同理弯予，如果nums[mid] < nums[mid + 1]，加上右邊負無窮槐瑞，所以mid的右邊一定會有峰值熙涤。
*
* @param nums
* @return
*/
public static int findPeakElement2(int[] nums) {
// 如果數(shù)組為空，則不存在峰值
if (nums == null) {
return -1;
}
// 如果數(shù)組的長度為1困檩，則首位即為峰值
if (nums.length == 1) {
return 0;
}
// 如果第一位比第二位大祠挫，則第一位必為峰值
if (nums[0] > nums[1]) {
return 0;
}
// 如果最后一位比倒數(shù)第二位大，則最后一位必為峰值
if (nums[nums.length - 1] > nums[nums.length - 2]) {
return nums.length - 1;
}
int left = 1, right = nums.length - 2;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void main(String[] args) {
int[] nums = {2, 4, 1, 2, 7, 8, 4};
System.out.println(findPeakElement(nums));
System.out.println(findPeakElement2(nums));
}
}
相信堅持的力量悼沿！
