原题:

 

 

最开始是照着提示的思路进行,中规中矩,用时64ms

 /** 
* @param {number[]} nums 
* @return {number} 
*/
var findPeakElement = function(nums) {  
  let i=0;
  let j=nums.length-1;
  let nums[-1]=nums[0]-1;
  let nums[nums.length]=nums[nums.length-1]-1;
  if(j===0) return 0;
  else if(j===1) return nums[0]>nums[1] ? 0 : 1;
  else{
    while(i<=j){
      if(nums[i]>nums[i-1] && nums[i]>nums[i+1]){
        return i;
      }else{
        i++
      }
      if(nums[j]>nums[j-1] && nums[j]>nums[j+1]){
        return j;
      }else{
        j--;
      }
      }
  }
};

然后想着优化,对着一个数组反复琢磨,发现一个规律:

  nums.length=0,1,2不谈,从nums.length>3开始,i=0,如果nums[i]>nums[i+1],直接得出第一个峰值;如果nums[i]<nums[i+1]则说明nums[i]不是峰值,而这恰恰就是关键,既然nums[i]不是峰值,必然有nums[i+1]>nums[i],那么当i=2的时候,就可以省略一次比较了,优化如下:

 /** 
* @param {number[]} nums 
* @return {number} 
*/
var findPeakElement = function(nums) {  
  let i=0;
  let j=nums.length-1;
  if(j===0) return 0;
  else if(j===1) return nums[0]>nums[1] ? 0 : 1;
  else{
    while(i<=j){
      if(nums[i]>nums[i+1]){
        return i;
      }else{
        i++
      }
      if(nums[j]>nums[j-1]){
        return j;
      }else{
        j--;
      }
      }
  }
};

不错了,用时60ms,那么还可以继续优化吗?

当然可以,在运行过程中,碰到return就直接结束了,那么不需要那么多的if-else

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    let i=0;
    let j=nums.length-1;
    if(j===0) return 0;
    if(j===1) return nums[0]>nums[1] ? 0 : 1;
    while(i<=j){
        if(nums[i]>nums[i+1]){
            return i;
        }
        else{
            if(nums[j]>nums[j-1]){
                return j;
            }
            i++;
            j--;
        }        
    }    
};

用时52ms,到此优化结束

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!