LeetCode算法题-Peak Index in a Moun

这是悦乐书的第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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！