LeetCode——Max Consecutive Ones
Question
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
解题思路
用stack求解。
具体实现
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
stack<int> st;
int max_len = 0;
for (int i : nums) {
if (i == 0) {
if (st.size() > max_len)
max_len = int(st.size());
// 清空栈
while(!st.empty())
st.pop();
} else
st.push(i);
}
return max(int(st.size()), max_len);
}
};
用一个计数器也可以求解。
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int max=0,cur=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]&1)
{
max=max>++cur?max:cur;
}
else cur=0;
}
return max;
}
};
时间复杂度都是O(n),但是计数器更快一些。