这是悦乐书的第329次更新，第352篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第199题（顺位题号是852）。如果以下属性成立，我们将数组A称为山：
A.length> = 3。
存在一个i(0 < i < A.length-1)，使得A[0] <A[1] <... A[i-1] < A[i] > A[i + 1]> ...> A[A.length - 1]。
给定一个绝对是山的数组，返回i，使得A[0] <A[1] <... A[i-1] <A[i]> A[i + 1]> ...> A [A.length - 1]。例如：
输入：[0,1,0]
输出：1
输入：[0,2,1,0]
输出：1
注意：
3 <= A.length <= 10000
0 <= A [i] <= 10 ^ 6
如上所述，A是一座山。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
数组A是座山的意思是指，数组A中的元素大小排列像山的形状一样，由低处到山顶，再由山顶到低处，而题目要求我们找的那个i就是山顶所在位置的索引，而题目给出的条件是，数组A肯定是一座山，所以可以直接使用遍历数组元素的方式，从第一位元素开始，往后比较，小于就继续往后，直到当前元素大于它的后一个元素，表示此元素就是山顶了，直接返回该元素索引即可。
public int peakIndexInMountainArray(int[] A) {
int n = A.length;
for (int i=0; i<n-1; i++) {
if (A[i] < A[i+1]) {
continue;
} else {
return i;
}
}
return 0;
}03 第二种解法
思路和上面一样，也是直接遍历数组元素，进行比较，找到山顶。
public int peakIndexInMountainArray(int[] A) {
int index = 0;
while (A[index] < A[index+1]) {
index++;
}
return index;
}03 第三种解法
上面两种解法的时间复杂度都是O(N)，我们还可以使用二分查找法，将时间复杂度降低为O(logN)。定义两个变量left、right，一个从0开始，一个从数组最后一位开始，每次取两者中间值，得到该中间位置的元素，然后和它的前一个元素比较大小，如果小于，说明还没有到山顶，需要继续向前，将中间值加1后赋值给left，反之就将中间值赋值给right。循环结束的条件是left不小于right，最后返回left即可。
public int peakIndexInMountainArray(int[] A) {
int left = 0, right = A.length-1;
while (left < right) {
int mid = left + (right-left)/2;
if (A[mid] < A[mid+1]) {
left = mid+1;
} else {
right = mid;
}
}
return left;
}04 小结
算法专题目前已日更超过五个月，算法题文章199+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
- 还没有人评论，欢迎说说您的想法！
客服
