牛牛的木板
题解
写法一:
我们先做一次前缀和
然后暴力枚举所有片段,判断这一段里黑色块数量时候小于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; } };