16

PHP 求解有效的山脉数组

 3 years ago
source link: https://hxd.life/2020/11/04/PHP-%E6%B1%82%E8%A7%A3%E6%9C%89%E6%95%88%E7%9A%84%E5%B1%B1%E8%84%89%E6%95%B0%E7%BB%84/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

PHP 求解有效的山脉数组

PHP 求解有效的山脉数组

author: he xiaodong date: 2020-11-04
有效的山脉数组

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

让我们回顾一下,如果 A 满足下述条件,那么它是一个山脉数组:

示例图
  • A.length >= 3
  • 在 0 < i < A.length - 1 条件下,存在 i 使得:
    • A[0] < A[1] < … A[i-1] < A[i]
    • A[i] > A[i+1] > … > A[A.length - 1]  

示例 1:

输入:[2,1]
输出:false

示例 2:

输入:[3,5,5]
输出:false

示例 3:

输入:[0,3,2,1]
输出:true

提示:

  • 0 <= A.length <= 10000
  • 0 <= A[i] <= 10000 

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/valid-mountain-array 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

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

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

class Solution {

    /**
     * @param Integer[] $A
     * @return Boolean
     */
    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;
    }
}

参考链接:

  1. 双指针法 总结篇

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券



About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK