牛牛的木板

题解

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

相关推荐

qq乃乃好喝到咩噗茶:院校后面加上211标签,放大加粗,招呼语也写上211
点赞 评论 收藏
分享
大方的大熊猫准备进厂:1.教育背景:你希望从事什么专业的工作你的主修课就是什么;成绩优秀是你应该做的,没什么可描述的,成绩不优秀也许人家在大学忙着创业呢?(成绩优秀不一定是好事,只能说明多元化的大学你上成了高中,没有真正上明白大学,反而体现了你死板,不爱社交,没有别的突出能力) 2.实践经历:你想表达的意思没有说清楚。你是说你会个性化服务,还是你有实习经历。如果没有带来,经济收益,表彰,更好的发展前景,那你还不如说说提升了自己哪些技能。你说有人给你送锦旗我都能明白你优秀,但是你说你会xxxx,你说这话谁信,证据呢。 3.入伍经历:你描述的就是你的工作职责或者你应该做的,并没有体现出来你把这个事情做好了,而且入伍经历并不能证明你能干好你要应聘的工作,不如只写经历其余所有内容都不写。 4.荣誉技能:重点突出一下,但不要过多描述,这些荣誉的含金量懂得都懂。 重点:你要应聘什么工作(具体岗位,实习生不具体),你的期望薪资
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务