寻找峰值
解题思路：
-
记满足题目要求的下标 i ，可以发现：
- arr[0] < arr[1] < … arr[i - 1] < arr[i]；
- arr[i] > arr[i + 1] > … > arr[arr.length - 1]；
-
可以转化为找到第一个 arr[i + 1] 小于 arr[i] 的 i 的位置（可以看做寻找 arr[i + 1] 小于 arr[i] 区间内的左边界）；
复杂度：
-
时间复杂度：O(logn)，其中 n 是数组 arr 的长度，需要进行二分查找的次数为O(logn)；
-
空间复杂度：O(1)；
代码实现：
function findPeakElement(nums: number[]): number {
let left = 0;
let right = nums.length - 1;
// 看做寻找 nums[i + 1] 小于 nums[i] 区间内的左边界，也就是第一个 nums[i + 1] 小于 nums[i] 的索引
while (left <= right) {
let mid = left + (right - left >> 1);
if (nums[mid] === nums[mid + 1]) {
right = mid - 1;
} else if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 题目数据保证 nums 是一个山脉数组，直接返回 left
return left;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
vue3🛫 ReactivityApi：reactive、readonly、ref 和 computed
上一篇
评论
