LeetCode485:Max Consecutive Ones 解答

刺骨的言语ヽ痛彻心扉 2022-06-07 08:11 157阅读 0赞

\#题目  
先来看一下题目：

> Given a binary array, find the maximum number of consecutive 1s in this >array.
> 
> The input array will only contain 0 and 1.  
> The length of input array is a positive integer and will not exceed 10,000  
> 题目的翻译是：给定一个二进制数组（也就是数组中只有0和1两种类型的元素），要求寻找数组中最大的连续的1的数目。  
> \#思路  
> 好久没有遇到这么简单的题目了，解这题的思路就是在遍历数组的同时维护两个变量：一个是当前连续的1的数目，另一个是目前为止整个数组连续的1的最大数目，如果遍历的元素是1，则更新这两个值，如果是0，则将当前连续的1的数目定为0；  
> 好，废话不多说，代码如下，也挺简洁的：

class Solution {
        public int findMaxConsecutiveOnes(int[] nums) {
            int max=0,curr=0;
            for(int iterator:nums){
                if(iterator==0){
                    curr=0;
                }else{
                    curr++;
                    if(curr>max)
                        max=curr;
                }
            }
            return max;
        }
    }

这个方法只需遍历一遍数组，accept之后显示runtime为9ms  
\#更好的办法  
提交了之后发现一个runtime只需7ms的解答，代码如下：

class Solution {
        public int findMaxConsecutiveOnes(int[] nums) {
            if(nums == null || nums.length < 1) return 0;
            int count = 0, temp = 0;
            for(int i=0; i<nums.length; i++){
                if(nums[i] == 0){
                    count = Math.max(count, temp);
                    temp = 0;
                }else{
                    temp++;
                }
            }
            count = Math.max(temp, count);
            return count;
        }
    }

跟我的代码不同之处在于我是当当前遍历的元素时1是比较max与temp的大小然后取较大的一个，它是当当前遍历的元素是0的时候才进行判断，毫无疑问，这样减少了判断的次数，减少了时间开销，是一个更优的解法，也难怪它的runtime才7ms，棒！