golang刷leetcode 滑动窗口（1）
golang刷leetcode 滑动窗口（1）
golangLeetcode
发布于 2022-08-02 15:53:12
发布于 2022-08-02 15:53:12
文章被收录于专栏：golang算法架构leetcode技术php
滑动窗口类题目基本上技巧在于维护一个滑动窗口，移动窗口的左右指针，使得窗口满足一定条件，关键在于如何处理窗口满足条件的地方，使得算法更高效。
最大连续1的个数
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。解题思路：
1，本题的要点不在滑动窗口长度，在于，维持窗口内0的个数<=K
2，我们定义指针l,r分别表示窗口左右下标，移动r，当A[r]＝＝0的时候我们增加0的个数记录sum，分两种情况
A,sum>K 这个时候需要移动左指针，让0的个数减1
B,sum<=K 无需处理，继续移动右指针
func longestOnes(A []int, K int) int {
if K==0 &&len(A)<1{
return 0
}
l:=0
sum:=0
max:=0
for r:=0;r<len(A);r++{
if A[r]==0{
sum++
if sum>K{
for A[l]!=0{
l++
}
l++
sum--
}
}
if r-l+1>max{
max=r-l+1
}
}
return max
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-03-15，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
