【LeetCode】162. Find Peak Element 解题记录
问题描述
A peak element is an element that is strictly greater than its neighbors.
Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞.
You must write an algorithm that runs in O(log n) time.
测试样例
1 | Input: nums = [1,2,3,1] |
说明
1 | Input: nums = [1,2,1,3,5,6,4] |
解题
思路
注意条件中的 nums[i] != nums[i + 1]
,即相邻元素不同
再考虑到 nums[-1] = nums[n] = -∞
则整个数组必有一个峰值,其左右元素均比它小,不管存在多少个波峰,我们寻找该峰值(实际上为最大值)即可
补充:
- 时间复杂度
O(logn)
代码
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 哆啦 C 梦!
评论