LeetCode 162. 寻找峰值

题目描述

🔥 162. 寻找峰值

image-20230308130618498

思路分析

为了找到峰值元素，我们可以使用二分查找的方法。具体思路如下：

  1. 初始化边界：设置 left 为 0，right 为 len(nums) - 1。
  2. 二分查找：
    • 计算中间索引 mid = (left + right) / 2。
    • 检查 nums[mid] 和其右侧元素 nums[mid + 1]：
      • 如果 nums[mid] < nums[mid + 1]，说明峰值在右侧，因此将 left 更新为 mid + 1。
      • 否则，说明峰值在左侧或当前元素就是峰值，因此将 right 更新为 mid。
  3. 结束条件：当 left 等于 right 时，返回 left 作为峰值的索引。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

func findPeakElement(nums []int) int {
	left, right := 0, len(nums)-1

	for left < right {
		mid := (left + right) / 2
		// 如果中间元素小于右侧元素，说明峰值在右侧
		if nums[mid] < nums[mid+1] {
			left = mid + 1
		} else {
			// 否则，峰值在左侧或当前元素就是峰值
			right = mid
		}
	}

	return left
}
  • 时间复杂度：O (log n)，因为每次都将搜索范围缩小一半。
  • 空间复杂度：O (1)，只使用了常数级别的额外空间。

🍏 点击查看 Java 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/09730219
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！