题目描述
思路解析动画文字版
记牢这一句:窗口里少数派的个数就是要翻转的次数,这个次数不超过 k,窗口就合法。少数派超了就从左边缩,缩到刚好合法为止。下面每一帧都在套这句话。
先把整串摆出来,下标从 0 到 7 依次是 T T F T T F T T。我们要从左往右滑一个窗口,窗口里数着 T 和 F 各多少个。右边这张小面板就是窗口内的统计,现在窗口还没开张,两个计数都是 0。开始读入字符。
把右端下标 0 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 1 个,F 有 0 个,少数派是 0 个。少数派 0 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..0] 现在合法,大小是 1,里面翻掉少数派的 0 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 1。
把右端下标 1 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 2 个,F 有 0 个,少数派是 0 个。少数派 0 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..1] 现在合法,大小是 2,里面翻掉少数派的 0 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 2。
把右端下标 2 的字符 F 读进窗口,它的计数加一。现在窗口里 T 有 2 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..2] 现在合法,大小是 3,里面翻掉少数派的 1 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 3。
把右端下标 3 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 3 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..3] 现在合法,大小是 4,里面翻掉少数派的 1 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 4。
把右端下标 4 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 4 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [0..4] 现在合法,大小是 5,里面翻掉少数派的 1 个字符就能全部相同。它比之前见过的都长,刷新历史最长 ans = 5。
把右端下标 5 的字符 F 读进窗口,它的计数加一。现在窗口里 T 有 4 个,F 有 2 个,少数派是 2 个。少数派 2 已经 > k = 1,窗口暂时不合法,得从左边缩一缩。
窗口不合法,从最左边把下标 0 的 T 踢出去,左指针右移到 1。现在窗口里 T 有 3 个,F 有 2 个,少数派 2 个。少数派还是 2 个,仍然 > k = 1,继续往右踢。
窗口不合法,从最左边把下标 1 的 T 踢出去,左指针右移到 2。现在窗口里 T 有 2 个,F 有 2 个,少数派 2 个。少数派还是 2 个,仍然 > k = 1,继续往右踢。
窗口不合法,从最左边把下标 2 的 F 踢出去,左指针右移到 3。现在窗口里 T 有 2 个,F 有 1 个,少数派 1 个。少数派 1 ≤ k = 1,终于合法了,可以停下来结算。
结算这一步。窗口 [3..5] 现在合法,大小是 3,里面翻掉少数派的 1 个字符就能全部相同。它没有超过历史最长 5,ans 保持不动,窗口继续往右滑。
把右端下标 6 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 3 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [3..6] 现在合法,大小是 4,里面翻掉少数派的 1 个字符就能全部相同。它没有超过历史最长 5,ans 保持不动,窗口继续往右滑。
把右端下标 7 的字符 T 读进窗口,它的计数加一。现在窗口里 T 有 4 个,F 有 1 个,少数派是 1 个。少数派 1 ≤ k = 1,窗口还合法,先放着,等下结算。
结算这一步。窗口 [3..7] 现在合法,大小是 5,里面翻掉少数派的 1 个字符就能全部相同。它没有超过历史最长 5,ans 保持不动,窗口继续往右滑。
整串滑完了。见过的最长合法窗口是 [0..4],也就是 TTFTT 这一段。它里面只有 1 个 F,把这个 F 翻成 T,整段就变成 5 个连续的 T,正好用掉 1 次操作。所以答案就是 5,跟开头看出来的对上了。
边界想清:k 为 0 时答案等于原串最长同字符段、k 够大时能翻成全长、本来全相同则直接是全长。
面试重点:变长窗口加少数派受限、和最大连续 1 的个数 III 同源、两趟法与单窗口法等价。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int: def f(c: str) -> int: cnt = l = 0 for ch in answerKey: cnt += ch == c if cnt > k: cnt -= answerKey[l] == c l += 1 return len(answerKey) - l return max(f("T"), f("F"))复杂度
- 时间：O(n)，n 是字符串长度。单窗口法里每个下标最多被右指针读入一次、被左指针踢出一次,合计每个字符常数次操作;参考代码的两趟法各扫一遍,仍是线性
- 空间：O(1)，只用到 cntT、cntF、l、ans 这几个计数变量,不随字符串变长而增加。参考代码三种语言都直接在原字符串上按下标读字符(Java 用 charAt),不额外开数组,空间同为常数
易错点
面试追问把动画讲成自己的话
追问这题的核心结构是什么?
追问它和最大连续 1 的个数 III 是一回事吗?
追问参考代码为什么写成两趟?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分配给商店的最多商品的最小值
LeetCode 2064 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题