Java教程

双指针算法

本文主要是介绍双指针算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.有效的山脉数组

 给定一个有效的整数数组A。如果它是有效的山脉数组就返回true,否则返回false。

 数组A

A.length>=3;

在0<i<A.length-1 条件下 存在i 

(1)A[0]<A[i] <....<.A[i-1]<A[i];

(2)A[i]>A[i+1]>....>A[A.length-1];

解题思路:

双指针  一个往前跑 一个从后往前跑 最终相遇在中间就可以了。

临界条件: 如果 left 或者 right 没有移动,说明是一个单调递增或者递减的数组。则依然不是删峰。

$a=[1,2,3,4,5,3,2,1];
function validMountainArray($a)
{
    if(count($a)<3){
        return false;

    }
    $left = 0;
    $right = count($a)-1;
    while($left < count($a)-1 && $a[$left]<$a[$left+1] ){
        $left++;
    }
    while($right >0 && $a[$right]<$a[$right-1]){
        $right--;
    }
    //如果left 或者 right 都在起始位置,说明不是山峰
    if($left==$right && $left!=0 && $right!=count($a)-1){
        return true;
    }
    return false;
}
print_r(validMountainArray($a));

 

这篇关于双指针算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!