符合下列属性的数组 arr 称为 山脉数组 :arrlength = 3存在 i0 i arrlength - 1使得:arr0 arr1 arri-1 arriarri arri+1 arrarrlength - 1给你由整数组成的山脉数组 arr 返回满足 arr0 arr1 arri - 1 arri arri + 1 arrarrlength - 1 的
二分和三分都可以解决这个问题,但是二分法更快。
二分法的思路是不断缩小查找范围,每次取中间的元素,判断其与相邻元素的关系。如果中间元素比其前一个元素和后一个元素都大,那么这个元素就是山脉数组的峰值。如果中间元素比其前一个元素小,说明峰值在左侧,将查找范围缩小到左侧;如果中间元素比其后一个元素小,说明峰值在右侧,将查找范围缩小到右侧。不断缩小范围,直到找到峰值。
时间复杂度为O(log(n)),其中n为数组的长度。
原文地址: https://www.cveoy.top/t/topic/iD9m 著作权归作者所有。请勿转载和采集!