#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.分析:題目是為了尋找一個(gè)高峰元素，所謂高峰元素要大于兩邊元素，如果有多處高峰，返回其中任意的一個(gè)下標(biāo)。所謂的高峰不就是：1】連續(xù)單調(diào)增，過了某個(gè)元素，連續(xù)單調(diào)減的元素，2】連續(xù)單調(diào)減，過了某個(gè)元素，連續(xù)單調(diào)增題目默認(rèn)所有元素不用。也可以這樣認(rèn)為，求出當(dāng)前元素和前一個(gè)元素的斜率k1,求出當(dāng)前元素和后一個(gè)元素的斜率為k2，如果k1*k2 < 0,說明當(dāng)前元素為高峰元素，由于num[-1]和num[n]已經(jīng)確認(rèn)第一個(gè)元素和之前的元素的k是正值，最后一個(gè)元素和num[n]的斜率k為負(fù)值Note:Your solution should be in logarithmic complexity.暴力破解，遍歷一遍即可，時(shí)間復(fù)雜度為O(n)。目前需要的時(shí)間復(fù)雜度為O(logN)，這種明顯應(yīng)該是基于二分查找的情況。如果中間的元素大于兩側(cè)元素，直接返回；否則，應(yīng)該遍歷左半部分，還是右半部分1】 左側(cè)元素 > 中間元素，左半部分必定有峰值，向左查找2】右側(cè)元素 > 中間元素，右側(cè)部分必定有峰值，向右側(cè)查找如果只有兩個(gè)元素，輸入:4(元素個(gè)數(shù))1 2 3 178 7 6 3 5 7 673 4 5 6 8 7 671 2 3 4 5 6 711輸出:20460關(guān)鍵:1 如果中間的元素大于兩側(cè)元素，直接返回；否則，應(yīng)該遍歷左半部分，還是右半部分1】 左側(cè)元素 > 中間元素，左半部分必定有峰值，向左查找2】右側(cè)元素 > 中間元素，右側(cè)部分必定有峰值，向右側(cè)查找*/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;//造成進(jìn)位，當(dāng)前元素mid不可能				}				else				{					low = mid + 1;				}			}			//沒有找到			else if(mid - 1 >= 0)			{				//左邊 < 當(dāng)前				if(nums.at(mid-1) < nums.at(mid))				{					return mid;				}				//左邊 > 當(dāng)前，向左邊尋找				else				{					high = mid - 1;				}			}			else if(mid + 1 < size)			{				if(nums.at(mid+1) < nums.at(mid))				{					return mid;				}				//右邊 > 當(dāng)前，右邊尋找				else				{					low = mid + 1;				}			}			//只有一個(gè)元素，返回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;}