Max Consecutive Ones
Given a binary array, find the maximum number of consecutive 1s in this array.
1. The input array will only contain 0 and 1.
2. The length of input array is a positive integer and will not exceed 10,000
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.
Use two pointers, left and right.
The left pointer is to find the bit is 1
The right porinter is start from left pointer to find the end of this consecutive ones.
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int len = nums.length;
int left = 0;
int right = 0;
int result = 0;
while (true) {
while (left < len && nums[left] == 0) {
left++;
}
if (left == len) {
break;
}
right = left + 1;
while (right < len && nums[right] == 1) {
right++;
}
result = Math.max(result, right - left);
if (right == len) {
break;
}
left = right;
}
return result;
}
}
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int len = nums.size();
int left = 0;
int right = 0;
int result = 0;
while (true) {
while (left < len && nums[left] == 0) {
left++;
}
if (left == len) {
break;
}
right = left + 1;
while (right < len && nums[right] == 1) {
right++;
}
result = max(result, right - left);
if (right == len) {
break;
}
left = right;
}
return result;
}
};
class Solution(object):
def findMaxConsecutiveOnes(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
numLen, left, right, result = len(nums), 0, 0, 0
while True:
while left < numLen and nums[left] == 0:
left += 1
if left == numLen:
break
right = left + 1
while right < numLen and nums[right] == 1:
right += 1
result = max(result, (right - left))
if right == numLen:
break
left = right
return result
int findMaxConsecutiveOnes(int* nums, int numsSize) {
int len = numsSize;
int left = 0;
int right = 0;
int result = 0;
while (true) {
while (left < len && nums[left] == 0) {
left++;
}
if (left == len) {
break;
}
right = left + 1;
while (right < len && nums[right] == 1) {
right++;
}
int diff = right - left;
result = result < diff ? diff : result;
if (right == len) {
break;
}
left = right;
}
return result;
}
- Time Complexity: O(N), N is the length of array.
- Space Complexity: O(1)