/*********************************
*   日期：2015-01-31
*   作者：SJF0115
*   题目: 162.Find Peak Element
*   网址：www.2cto.com
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include 
  
   
#include 
   
     #include 
    
      using namespace std; class Solution { public: int findPeakElement(const vector
     
       &num) { int size = num.size(); if(size == 1){ return 0; }//if // 判断第一个元素和最后一个元素 if(size > 1){ if(num[0] > num[1]){ return 0; }//if if(num[size-1] > num[size-2]){ return size-1; }//if }//if for(int i = 1;i < size-1;++i){ if(num[i] > num[i-1] && num[i] > num[i+1]){ return i; }//if }//for } }; int main(){ Solution solution; // vector
      
        num = {1,2,3,1}; //vector
       
         num = {4,3,3,1}; vector
        
          num = {1,2,3,4}; int result = solution.findPeakElement(num); // 输出 cout<
          
          
          
?
          
【分析二】
          
?
          
 根据给出的条件： num[i] != num[i+1], 相邻两个元素不相等。运用二分查找原理。
          
 （1）如果 num[i-1] < num[i] > num[i+1], 则num[i] 就是 peak
          
 （2）如果 num[i-1] < num[i] < num[i+1], 则 num[i+1...n-1] 必定包含一个 peak
          
 （3）如果 num[i-1] > num[i] > num[i+1], 则num[0...i-1] 必定包含一个 peak
          
 （4）如果 num[i-1] > num[i] < num[i+1], 则 两边都有一个 peak
          
 继续优化一下，通过上面仔细观察一下：
          
?
          
 （1）如果 num[i-1] < num[i] > num[i+1], 则num[i] 就是 peak
          
 （2）如果 num[i-1] < num[i] , 则 num[i+1...n-1] 必定包含一个 peak，left指向mid+1
          
 （3）如果 num[i-1] > num[i] , 则num[0...i-1] 必定包含一个 peak,right指向mid-1
          
【代码二】
          
?
          
    /*------------------------------------
    *   日期：2015-01-31
    *   作者：SJF0115
    *   题目: 162.Find Peak Element
    *   网址：https://oj.leetcode.com/problems/find-peak-element/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------*/
    #include 
           
            
    #include 
            
              #include 
             
               using namespace std; class Solution { public: int findPeakElement(const vector
              
                &num) { int size = num.size(); // only one element if (size == 1) { return 0; }//if int left = 0, right = size - 1; int mid; // left right 距离为1 退出 while (left < right - 1) { mid = left + (right - left) / 2; // If num[i-1] < num[i] > num[i+1],then num[i] is peak if (num[mid] > num[mid - 1] && num[mid] > num[mid + 1]) { return mid; }//if // If num[i-1] < num[i],then num[i+1...n-1] must contains a peak if (num[mid - 1] < num[mid]) { left = mid + 1; }//if // If num[i-1] > num[i], then num[0...i-1] must contains a peak else { right = mid - 1; }//else }//while return num[left] > num[right] ? left : right; } }; int main(){ Solution solution; vector
               
                 num = {1,2,3,1}; //vector
                
                  num = {4,3,3,1}; //vector
                 
                   num = {2,3,1,4,2,1}; int result = solution.findPeakElement(num); // 输出 cout<
                  
                   
【分析三】
                   
递归版
                   
【代码三】
                   
?
                   
?
                   
    /*------------------------------------
    *   日期：2015-01-31
    *   作者：SJF0115
    *   题目: 162.Find Peak Element
    *   网址：www.2cto.com
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------*/
    #include 
                    
                     
    #include 
                     
                       #include 
                      
                        using namespace std; class Solution { public: int findPeakElement(const vector
                       
                         &num) { return helper(num,0,num.size()-1); } private: int helper(const vector
                        
                          &num,int left,int right){ // only one element if(left == right){ return left; }//if // neighbor if(left == right - 1){ return num[left] > num[right] ? left : right; }//if int mid = left + (right - left) / 2; // If num[i-1] < num[i] > num[i+1], then num[i] is peak if(num[mid] > num[mid-1] && num[mid] > num[mid+1]){ return mid; }//if // If num[i-1] > num[i], then num[0...i-1] must conta