数据规模高达5 *104,我们只能使用O(n)的算法了。
可以想到的就是滑动窗口(sliding window)，由于最长长度未知，我们可以使用动态滑动窗口。
记录当前滑动窗口中T和F出现的次数，如果其中较少的一个<=k，那么就可以全部替换它，使得整个滑动窗口都变成相同的值。如果这个时候滑动窗口长度大于当前最大长度，我们就把滑动窗口变大，右侧+1，并更新最大长度。否则，减少滑动窗口，左侧-1。
时间复杂度：O(n)
空间复杂度：O(2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public: int maxConsecutiveAnswers(string_view A, int k) { int ans = 0; int f = 0; array<int, 2> count; // number of 'F' and 'T' in the sliding window for (int i = 0; i < A.size(); ++i) { ++count[A[i] == 'T']; if (min(count[0], count[1]) <= k && count[0] + count[1] > ans) ++ans; else --count[A[i - ans] == 'T']; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment