博文中会简要介绍Leetcode P0162题目分析及解题思路。
“Find Peak Element”是一道比较经典的二分查找题。解决这道问题的核心在于找到合适的二分搜索方法和条件。
A peak element is an element that is greater than its neighbors.
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
这道题的思路围绕二分搜索展开。二分搜索的核心在于如何比较元素。如果我们知道比较元素的方法，自然我们就可以得到所寻找的结果。在这道题里，一个极大值点代表其左右邻居的值小于它自身的值。有如下情况会出现，
- 当前值恰好是极大值，则直接返回下标。
- 当前值大于左边，那么右边一定存在一个极大值。因为数组的边界都是负无穷，即便右边是个单调递增序列，数组最末尾的值依旧是极大值。其大于它的前一个数，同时也大于负无穷。
- 同理，当前值大于右边，那么就在左边搜索。
- 若当前值同时小于左边和右边，则任取一边搜索即可。
以下是Java的题解代码实现。
class Solution {
public int findPeakElement(int[] nums) {
int N = nums.length;
if (N == 1)
return 0;
int left = 0, right = N-1, mid = 0;
while (left <= right) {
mid = (left+right)/2;
int leftNum = (mid > 0)? nums[mid-1]: Integer.MIN_VALUE;
int rightNum = (mid < N-1)? nums[mid+1]: Integer.MIN_VALUE;
if (nums[mid] > leftNum && nums[mid] > rightNum)
return mid;
else if (nums[mid] >= leftNum) {
left = mid+1;
}
else if (nums[mid] >= rightNum) {
right = mid-1;
}
else {
right = mid-1;
}
}
return mid;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int N = nums.size();
if (N == 1)
return 0;
int left = 0, right = N-1, mid = 0;
while (left <= right) {
mid = (left+right)/2;
int left_num = (mid > 0)? nums[mid-1]: INT_MIN;
int right_num = (mid < N-1)? nums[mid+1]: INT_MIN;
if (nums[mid] > left_num && nums[mid] > right_num) {
return mid;
}
else if (nums[mid] >= left_num) {
left = mid+1;
}
else if (nums[mid] <= right_num) {
right = mid-1;
}
else {
right = mid-1;
}
}
return mid;
}
};