Leetcode162. 寻找峰值

本文主要是介绍Leetcode162. 寻找峰值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Every day a Leetcode

题目来源：162. 寻找峰值

解法1：STL

代码：

class Solution {
public:int findPeakElement(vector<int>& nums) {return max_element(nums.begin(), nums.end()) - nums.begin();}
};

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

解法2：二分查找

代码：

/** @lc app=leetcode.cn id=162 lang=cpp** [162] 寻找峰值*/// @lc code=start// 二分查找// class Solution
// {
// public:
//     int findPeakElement(vector<int> &nums)
//     {
//         int n = nums.size();
//         int left = 0, right = n - 1;
//         int ans = -1;
//         while (left <= right)
//         {
//             int mid = (left + right) / 2;
//             // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
//             // 方便处理 nums[-1] 以及 nums[n] 的边界情况
//             function<pair<int, int>(int)> get = [&](int index) -> pair<int, int>
//             {
//                 if (index == -1 || index == n)
//                     return {0, 0};
//                 return {1, nums[index]};
//             };
//             if (get(mid - 1) < get(mid) && get(mid) > get(mid + 1))
//             {
//                 ans = mid;
//                 break;
//             }
//             if (get(mid) < get(mid + 1))
//                 left = mid + 1;
//             else
//                 right = mid - 1;
//         }
//         return ans;
//     }
// };class Solution
{
public:int findPeakElement(vector<int> &nums){int n = nums.size();int left = 0, right = n - 1;while (left < right){int mid = (left + right) / 2;if (nums[mid] > nums[mid + 1])right = mid; // 峰顶行号 <= ielseleft = mid + 1; // 峰顶行号 > i}return left;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(log⁡n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

拓展题：Leetcode 1901. 寻找峰值 II

链接：1901. 寻找峰值 II

二分包含峰顶的行号 i：

• 如果 mat[i] 的最大值比它下面的相邻数字小，则存在一个峰顶，其行号大于 iii。缩小二分范围，更新二分区间左端点 left。
• 如果 mat[i] 的最大值比它下面的相邻数字大，则存在一个峰顶，其行号小于或等于 i。缩小二分范围，更新二分区间右端点 right。

代码：

/** @lc app=leetcode.cn id=1901 lang=cpp** [1901] 寻找峰值 II*/// @lc code=start// 二分查找class Solution
{
public:vector<int> findPeakGrid(vector<vector<int>> &mat){if (mat.empty())return {};int m = mat.size(), n = mat[0].size();int left = 0, right = m - 1;while (left < right){int i = (left + right) / 2;int j = indexOfRowMax(mat[i]);if (mat[i][j] > mat[i + 1][j])right = i; // 峰顶行号 <= ielseleft = i + 1; // 峰顶行号 > i}return {left, indexOfRowMax(mat[left])};}// 辅函数 - 返回行中最大元素的下标int indexOfRowMax(const vector<int> &row){return max_element(row.begin(), row.end()) - row.begin();}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(nlog⁡m)，其中 m 和 n 分别为 mat 的行数和列数。需要二分 O(log⁡m) 次，每次二分需要 O(n) 的时间寻找 mat[i] 最大值的下标。
空间复杂度：O(1)。仅用到若干额外变量。

这篇关于Leetcode162. 寻找峰值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---