LeetCode 1004. 最大连续1的个数 III
题目描述
思路分析
滑动窗口问题
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestOnes(nums []int, k int) int {
left, right := 0, 0
zeroCount := 0
res := 0
for right < len(nums) {
if nums[right] == 0 {
zeroCount++
}
for zeroCount > k {
if nums[left] == 0 {
zeroCount--
}
left++
}
res = max(res, right-left+1)
right++
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func longestOnes(nums []int, k int) int {
left := 0
countZero := 0
res := 0
for right := 0; right < len(nums); right++ {
if nums[right] == 0 {
countZero++
}
// 如果 0 的个数超过 k，左指针右移，直到 0 的个数小于等于 k
for countZero > k {
if nums[left] == 0 {
countZero--
}
left++
}
// 更新最大长度
res = max(res, right-left+1)
}
return res
}
- 时间复杂度：O(n)，每个元素最多进出窗口一次。
- 空间复杂度：O(1)，只用了常数个变量。
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！