Cool说丨力扣162

162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引

数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = [1,2,3,1]输出: 2解释: 3 是峰值元素,你的函数应该返回其索引 2。示例 2:

输入: nums = [1,2,1,3,5,6,4]输出: 1 或 5 解释: 你的函数可以返回索引 1,其峰值元素为 2; 或者返回索引 5, 其峰值元素为 6。

第一版,直接暴力法

执行用时 :8 ms, 在所有 C++ 提交中击败了73.77%的用户

内存消耗 :8.7 MB, 在所有 C++ 提交中击败了69.45%的用户

int findPeakElement(vector<int>& nums) {

if (nums.size() <= 1) return 0;

if (nums[1] < nums[0]) return 0;

if (nums[nums.size() - 2] < nums[nums.size() - 1]) return nums.size() - 1;

int temp = 0;

for (int i = 1; i <= nums.size() - 2;++i) {

if(nums[i]> nums[i-1] && nums[i]>nums[i + 1]) return i;

}

return 0;

}

第二版 二分法模板

low<=high

low=mid+1;

high=mid-1;

结束时,low在high前面一个元素了,差值为0和1时都会继续执行,需要注意边界问题

int findPeakElement(vector<int>& nums) {

if (nums.size() <= 1) return 0;

if (nums[0] > nums[1]) {

return 0;

}

if (nums[nums.size() - 1] > nums[nums.size() - 2]) {

return nums.size() - 1;

}

int l = 0,r = nums.size() - 1;

while (l <= r) {

int m = (l + r) / 2;

if (m > 0 and nums[m - 1] > nums[m]) {

r = m-1;

}

else if (m < nums.size() and nums[m + 1] > nums[m]) {

l = m+1;

}

else {

return m;

}

}

return l;

}