牛牛的木板
题解
写法一:
我们先做一次前缀和
然后暴力枚举所有片段,判断这一段里黑色块数量时候小于m,小于则记录答案。时间复杂度
写法二
我们考虑使用队列来模拟一下。
假设我们现在有一段(L--R)的木板
假设R+1是白色 我们可以直接拓展
假设R+1是黑色 我们可以通过洗刷一次使其变成白色 然后拓展
但是如果已经没有机会洗刷了呢?
这意味着R无法拓展了,我们只能考虑放弃L的位置 使L向L+1拓展。
因为这样才会有新贡献的可能,于是我们可以通过队列来模拟这个过程。双指针也是可以的。
时间复杂度
class Solution {
public:
/**
*
* @param n int整型
* @param m int整型
* @param a int整型vector
* @return int整型
*/
int solve(int n, int m, vector<int>& a) {
// write code here
int cnt=0,ans=0;
queue<int>q;
for (int i=0; i<n; i++)
{
if (a[i]==1)
{
q.push(1);
int sz=q.size();
ans=max(ans,sz);
}
else
{
q.push(0);
cnt++;
while (cnt>m)
{
int x=q.front();
if (x==0) cnt--;
q.pop();
}
}
}
return ans;
}
}; 

