162. Find Peak Element
1. Description
A peak element is an element that is strictly greater than its neighbors.
Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞.
2. Example
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
3. Constraints
- 1 <= nums.length <= 1000
- $-2^{31}$ <= nums[i] <= $2^{31} - 1$
- nums[i] != nums[i + 1] for all valid i.
4. Follow Up
- Could you implement a solution with logarithmic complexity?
5. Solutions
My Accepted Solution(Follow Up)
n = i_nums.size()
Time complexity: O($log_2n$)
Space complexity: O(1)
// it's time complexity should be logarithmic, so we need the binary search algorithm
class Solution {
public:
int findPeakElement(const vector<int>& i_nums) {
if (i_nums.size() == 1) {
return 0;
}
int peakIndex = INT_MIN;
i_nums.push_back(INT_MIN); // we push a min value to the end to simplify the border check
// it will be helpful to push a min value to the front as well
// but it will move all elements and result in a O(n) time complexity
for (int left = 0, right = i_nums.size() - 1; left < right;) {
int middle = left + (right - left) / 2;
if (middle == 0 && i_nums[middle] > i_nums[middle + 1] ||
middle > 0 && i_nums[middle] > i_nums[middle - 1] &&
i_nums[middle] > i_nums[middle + 1]) {
peakIndex = middle;
break;
}
// we just need to find any peak value, so if the element is a vally point
// we don't care we get the left peak or the right peak
i_nums[middle] < i_nums[middle - 1] ? right = middle : left = middle;
}
return peakIndex;
}
};