【LeetCode】山脉数组的峰顶索引 Java 题解

关注

发布于: 2021 年 06 月 15 日

题目描述

符合下列属性的数组 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
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这个题目是简单题目，题干比较长，分析之后，就是找数组中的最大值。解法比较多，可以先用朴素解法求解，在进行优化。

AC 代码

    public int peakIndexInMountainArray(int[] arr) {        int ans = 0;
        for (int i = 1; i < arr.length; i++) {            if (arr[i] > arr[ans]) {                ans = i;            }        }
        return ans;    }

复制代码

朴素解法的时间复杂度是 O(n), 空间复杂度是 O(1)

    public int peakIndexInMountainArray(int[] arr) {        int ans = 0;
        for (int i = 1; i < arr.length; i++) {            if (arr[i] > arr[ans]) {                ans = i;            } else {                break;            }        }
        return ans;    }

复制代码

优化后朴素解法的时间复杂度是 O(n), 空间复杂度是 O(1)

    public int peakIndexInMountainArray(int[] arr) {        int n = arr.length;        int left = 1, right = n - 2, ans = 0;        while (left <= right) {            int mid = left + (right - left) / 2;            if (arr[mid] > arr[mid + 1]) {                ans = mid;                right = mid - 1;            } else {                left = mid + 1;            }        }        return ans;    }

复制代码

二分查找解法的时间复杂度是 O(log(n)), 空间复杂度是 O(1)

总结

二分查找不仅可以查找全部有序的数组，也可以查找局部有序的数组，提升查询效率。
坚持每日一题，加油！

发布于: 2021 年 06 月 15 日阅读数: 7

原文链接:【http://xie.infoq.cn/article/09c775bebcc2eaccf85ad40ea】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】山脉数组的峰顶索引 Java 题解

题目描述

思路分析

AC 代码

总结

HQ数字卡

评论