leecode 解题总结：162. Find Peak Element

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题:A peak element is an element that is greater than its neighbors.Given an input array where num[i] ≠ num[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 num[-1] = num[n] = -∞.For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.click to show spoilers.Credits:Special thanks to @ts for adding this PRoblem and creating all test cases.分析:题目是为了寻找一个高峰元素，所谓高峰元素要大于两边元素，如果有多处高峰，返回其中任意的一个下标。所谓的高峰不就是：1】连续单调增，过了某个元素，连续单调减的元素，2】连续单调减，过了某个元素，连续单调增题目默认所有元素不用。也可以这样认为，求出当前元素和前一个元素的斜率k1,求出当前元素和后一个元素的斜率为k2，如果k1*k2 < 0,说明当前元素为高峰元素，由于num[-1]和num[n]已经确认第一个元素和之前的元素的k是正值，最后一个元素和num[n]的斜率k为负值Note:Your solution should be in logarithmic complexity.暴力破解，遍历一遍即可，时间复杂度为O(n)。目前需要的时间复杂度为O(logN)，这种明显应该是基于二分查找的情况。如果中间的元素大于两侧元素，直接返回；否则，应该遍历左半部分，还是右半部分1】 左侧元素 > 中间元素，左半部分必定有峰值，向左查找2】右侧元素 > 中间元素，右侧部分必定有峰值，向右侧查找如果只有两个元素，输入:4(元素个数)1 2 3 178 7 6 3 5 7 673 4 5 6 8 7 671 2 3 4 5 6 711输出:20460关键:1 如果中间的元素大于两侧元素，直接返回；否则，应该遍历左半部分，还是右半部分1】 左侧元素 > 中间元素，左半部分必定有峰值，向左查找2】右侧元素 > 中间元素，右侧部分必定有峰值，向右侧查找*/class Solution {public:	//查找	int search(vector<int>& nums ,int low ,int high)	{		if(nums.empty() || low < 0 || high >= nums.size())		{			return 0;		}		int mid;		int size = nums.size();		bool isLeftOk = false;		bool isRightOk = false;		while(low < high)		{			mid = low + (high - low)/2;			if( mid - 1 >= 0 && mid + 1 < size)			{				//如果不符合				if(nums.at(mid-1) < nums.at(mid) && nums.at(mid) > nums.at(mid+1))				{					return mid;				}				//向左查找				else if(nums.at(mid-1) > nums.at(mid))				{					high = mid - 1;//造成进位，当前元素mid不可能				}				else				{					low = mid + 1;				}			}			//没有找到			else if(mid - 1 >= 0)			{				//左边 < 当前				if(nums.at(mid-1) < nums.at(mid))				{					return mid;				}				//左边 > 当前，向左边寻找				else				{					high = mid - 1;				}			}			else if(mid + 1 < size)			{				if(nums.at(mid+1) < nums.at(mid))				{					return mid;				}				//右边 > 当前，右边寻找				else				{					low = mid + 1;				}			}			//只有一个元素，返回0			else			{				return 0;			}		}		return low;	}    int findPeakElement(vector<int>& nums) {        if(nums.empty() || 1 == nums.size())		{			return 0;		}		int index = search(nums , 0 , nums.size() - 1);		return index;    }};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 int result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 result = solution.findPeakElement(nums);		 cout << result << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}