【LeetCode】寻找峰值 Java 题解
题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
复制代码
思路分析
今天的每日一题,题目容易理解,首先可以通过朴素算法求解。
由于题目要求时间复杂度为 O(log n) 的算法,联想到二分查找算法。根据题意,比较相邻的两个数,代码如下:
通过代码
复制代码
总结
二分解法的时间复杂度是 O(log n), 空间复杂度是 O(1)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/576cda471f4a0d8a67ed80e54】。文章转载请联系作者。
评论