【Leetcode刷题Python】852. 山脉数组的峰顶索引

简介: 本文使用二分查找算法解决LeetCode "山脉数组的峰顶索引" 问题的Python实现,通过递归地缩小搜索区间来查找山脉数组的峰值索引。

1 题目

符合下列属性的数组 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

示例 2:

输入:arr = [0,2,1,0]
输出:1

2 解析

用二分查找的话,时间复杂度是Log(n)。思路是

  • 中间值大于后一个值的话,意思是已经爬坡过了峰值,那峰值一定在左边部分
  • 中间值小于后一个值的话,还在爬坡,峰值在右部分

3 Python实现

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left,right = 0,len(arr)-1
        result = 0
        while left<=right:
            mid = (left+right)//2
            if arr[mid]>arr[mid+1]:
                result = mid
                right = mid-1
            else:
                left = mid+1
        return result
目录
相关文章
|
算法 Python
<LeetCode天梯>Day009 两个数组的交集 II | 初级算法 | Python
<LeetCode天梯>Day009 两个数组的交集 II | 初级算法 | Python
<LeetCode天梯>Day009 两个数组的交集 II | 初级算法 | Python
|
算法 Python
<LeetCode天梯>Day005 旋转数组 (切片法) | 初级算法 | Python
<LeetCode天梯>Day005 旋转数组 (切片法) | 初级算法 | Python
<LeetCode天梯>Day005 旋转数组 (切片法) | 初级算法 | Python
|
算法 Python
<LeetCode天梯>Day007 存在重复元素 | 初级算法 | Python
<LeetCode天梯>Day007 存在重复元素 | 初级算法 | Python
<LeetCode天梯>Day007 存在重复元素 | 初级算法 | Python
|
算法 Python
<LeetCode天梯>Day041 打乱数组 | 初级算法 | Python
<LeetCode天梯>Day041 打乱数组 | 初级算法 | Python
<LeetCode天梯>Day041 打乱数组 | 初级算法 | Python
|
算法 Python
<LeetCode天梯>Day023 最长公共前缀(切片法) | 初级算法 | Python
<LeetCode天梯>Day023 最长公共前缀(切片法) | 初级算法 | Python
<LeetCode天梯>Day023 最长公共前缀(切片法) | 初级算法 | Python
|
存储 算法 Python
<LeetCode天梯>Day035 合并两个有序数组(切片法) | 初级算法 | Python
<LeetCode天梯>Day035 合并两个有序数组(切片法) | 初级算法 | Python
<LeetCode天梯>Day035 合并两个有序数组(切片法) | 初级算法 | Python
|
机器学习/深度学习 人工智能 Python
蓝桥杯 修改数组 python (并查集)
蓝桥杯 修改数组 python (并查集)
蓝桥杯 修改数组 python (并查集)
|
7月前
|
存储 Python
【Leetcode刷题Python】88. 合并两个有序数组
合并两个有序数组的方法:正向双指针法和逆向双指针法,都具有O(m+n)的时间复杂度,但前者的空间复杂度为O(m+n),后者的空间复杂度为O(1),并给出了Python语言的实现代码。
48 0
|
7月前
|
算法 Python
【Leetcode刷题Python】106.相交链表
采用双指针法来找出两个链表的相交起始节点,并详细解释了算法的时间和空间复杂度。
56 1
|
7月前
|
Python
【Leetcode刷题Python】108. 将有序数组转换为二叉搜索树
LeetCode上108号问题"将有序数组转换为二叉搜索树"的Python实现,通过递归选取数组中间值作为根节点,构建高度平衡的二叉搜索树。
45 2