牛牛的木板

题解

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

相关推荐

不愿透露姓名的神秘牛友
11-20 19:57
已编辑
某大厂 golang工程师 23.0k*16.0, 2k房补,年终大概率能拿到
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务