leetcode485--Max Consecutive Ones

leetcode485--Max Consecutive Ones

题目

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.
Note:

The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000


  • 理解

就是问中间有1的地方的最长的地方是多长,这个看完题目之后我想的是用两个指针,来记录这段1的长度,i,j,j 是快指针,如果遇到1的话,它就继续往前走,这时候i不动,遇到0的话,就把i归位到j的地方,每次遇到0的时候都更新当前的最大,注意最后返回的时候也要返回当前的最大和之前记录的最大中的最大者,因为可能从某个之后全部都是1了。

代码如下


class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if 0 not in nums:
            return len(nums)
       
        i,j  = 0,0
        
        maxnum = 0
        cur = 0
        while j<len(nums):
            if nums[j]==0:
                maxnum = max(maxnum, cur)
                j+=1
                cur = 0  # 更新当前的为0,重新记。
            else:
                j += 1
                cur += 1
        
        return max(maxnum, cur)

或者

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if 0 not in nums:
            return len(nums)
       
        i,j  = 0,0
        
        maxnum = 0
       
        while j<len(nums):
            if nums[j]==0:
                maxnum = max(maxnum, j-i)
                j+=1
                i = j
            else:
                j += 1
                
        
        return max(maxnum, j-i)
                

上面的办法有些花时,其实用一个指针就可以了。

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        Max = 0
        cur = 0
        
        for x in nums:
            if x:
                cur += 1
            else:
                Max = max(cur, Max)
                cur = 0
        return max(Max, cur)
                

用c++的话

class Solution{
    public:
        int findMaxConsecutiveOnes(vector<int>& nums){
            int result = 0, Max = 0;
            for(int i=0;i<nums.size(); i++)
                if(nums[i]){
                    result++;
                }else{
                    Max = max(Max, result);
                    result = 0;
                }
            return max(Max, result)

        }
};

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦