Leetcode基础刷题之PHP解析(128. Longest Consecutive Sequence)

2019-8-20 星期二 开始吧

好吧昨天没更新是因为被126题恶心到了，有点困难?，打算把126，127一样的题型放到后面，这道Hard的题和126根本没法比，给你们放张图

上一题链接Leetcode基础刷题之PHP解析(125. Valid Palindrome)

题目描述

这道题给定一个非排序的整形数组，求最长的连续序列长度。算法在O(n)的时间完成。

题目分析

其实这道题还是好理解的，如果是空直接返回0，否则可以先给数组排序，这样的话只需要遍历整个有序的数组，如果当前数和上一个数值一样的，不需要增加他的最长的长度，啥都不用处理，否则的话，只有两种情况，要么当前比上一个大1，要么不是，如果当前是等于上一个数+1,我们就更新当前最长的序列长度，否则的话我们就更新全局最长的长度，然后把当前最长的长度序列重新赋值,进行下一轮的统计。代码实现

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function longestConsecutive($nums) {
        if(empty($nums)) return 0;
        sort($nums);
        $max=1;
        $current=1;
        for($i=1;$i<count($nums);$i++){
            if($nums[$i] !=$nums[$i-1]){
                if($nums[$i] == $nums[$i-1]+1){
                    $current +=1;
                }else{
                    $max=max($current,$max);
                    $current=1;
                }
            }
        }
        return max($current,$max);
    }

可以自己思考一下为什么最后我们还需要比较全局最大长度和当前最大长度。